JS实现单源点最短路径、动态规划分段图算法

最近在上算法课（大三），因为自己是写js+php的，不想用c去写。在网上百度用js实现单源点最短路径、动态规划分段图算法这两个算法，发现并没有。。。于是自己xjb写了下，c里的带指针的结构体按我的理解换成了对象数组，写的不好请各位大牛给点改进的建议。。。

动态规划

 function createPoint(next,len,section){

        var o=new Object();

        o.next=next;

        o.len=len;

        o.section=section;

        return o;

    }



    var v1=createPoint([2,3,4,5],[9,7,3,2],1);

    var v2=createPoint([6,7,8],[4,2,1],2);

    var v3=createPoint([6,7],[2,7],2);

    var v4=createPoint([8],[11],2);

    var v5=createPoint([7,8],[11,8],2);

    var v6=createPoint([9,10],[6,5],3);

    var v7=createPoint([9,10],[4,3],3);

    var v8=createPoint([10,11],[5,6],3);

    var v9=createPoint([12],[4],4);

    var v10=createPoint([12],[2],4);

    var v11=createPoint([12],[5],4);

    var v12=createPoint([],[],5);



    var MAX=10000;

    function main(points,max_section) { //定义一个二维数组COST,如COST[4][9]表示第4段的v9这个点到终点的最短距离 var COST = new Array();

        for(var k=0;k1;k++){

            COST[k]=new Array();

            for(var j=0;j1;j++){

                COST[k][j]=MAX;

            }

        }

        var x=max_section;

        var i,j; //筛选section while(x>0){

            for(i=0;i-1){

                    if (points[i].section==max_section-1){

                        COST[x-1][i+1]=points[i].len[0];

                    }else{ //选个最小的路径 for (j=0;j-1][i+1])

                            COST[x-1][i+1]=points[i].len[j]+COST[x][points[i].next[j]];

                        }

                    }

                }

            }

            x--;

        }



        console.log(COST)

    }



    var points=[v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12];

    main(points,5); 

这是上面的图，这篇文章里的http://blog.csdn.net/ncepuzhu...

单源点最短路径

 function createPoint(next,len){ var o=new Object();

        o.next=next;

        o.len=len; return o;

    } function indexMin(arr) { var min = Math.min.apply(null,arr); //dist数组里的最小值的下标，即v几 return arr.indexOf(min);

    } var v0=createPoint([1,2,3],[20,50,30]); var  v1=createPoint([2,5],[25,70]); var v2=createPoint([4,5],[25,50]); var v3=createPoint([4],[55]); var v4=createPoint([5,6],[10,70]); var v5=createPoint([6],[50]); var v6=createPoint([],[]); var nodes=[v0,v1,v2,v3,v4,v5,v6]; var MAX=10000; //nodes为点集合 function dijkstra(nodes){ var dist=Array.apply(null, Array(nodes.length)).map(() => MAX) //s为已选取的结点集合 0表示还不在 1表示在 var s=Array.apply(null,Array(nodes.length)).map(()=>0);

        s[0]=1; var i,min; //从源点v0出发，选个最短的路径 //先判断源点是否与其他点相邻接 if (nodes[0].next===undefined||nodes[0].next==0){ console.log("源点没有邻接点"); return;

        } for (i=0;i0].next.length;i++){

            dist[nodes[0].next[i]]=nodes[0].len[i]

        } //dist数组里的最小值的下标，即v几 var min_index=indexMin(dist);

        s[min_index]=1; while(min_index){ for (i=0;i//            console.log(nodes[min_index].next[i]) if (nodes[min_index].len[i]+dist[min_index]//                    console.log(nodes[min_index].next[i]) dist[nodes[min_index].next[i]]=nodes[min_index].len[i]+dist[min_index]

                }

            } var arr=Array.apply(null, Array(nodes.length)).map(() => MAX); for (i=0;iif (s[i]!=1){

                    arr[i]=dist[i]

                }

            } //            console.log(arr) min = Math.min.apply(null,arr); //dist数组里的最小值的下标，即v几 min_index = arr.indexOf(min); //            console.log(min_index) s[min_index]=1; console.log(s) if (!s.indexOf(0)){ return dist;

            } console.log(dist)

        }



    }

    dijkstra(nodes)

本来想用矩阵（二维数组）来存储图的，但是想到每次都要循环找数，似乎有点麻烦。就用这样的对象数组了