dijkstra和floyd

图的单源最短路径和多源最短路径

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
初始时，S(已求出最短路径的顶点)中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

function dijkstra(data, source) {
    // dist存放路径距离，path存放父顶点，visit存放访问过的顶点
    var dist = [], path = [], visit = [];   
    var len = data.length;
    // 初始化
    for (var i = 0; i < len; i++) {
        dist[i] = data[source][i];  // 源点到相邻顶点的权值
        path[i] = source;
        visit[i] = false;
    }
    dist[source] = 0;
    visit[source] = true;

    for (var i = 1; i < len; i++) {     // 除去源点的各顶点
        // 寻找下个顶点到各顶点最小的路径；
        var min = {idx: -1, weight: Infinity};  // 下标，权重
        for (var j = 0; j < len; j++) {
            if ( false === visit[j] && dist[j] < min.weight )
                min = {idx: j, weight: dist[j]};
        }

        visit[ min.idx ] = true;

        // 更新dist
        for (var k = 0; k < len; k++) {
            if ( false ===  visit[k] 
                && min.weight + data[min.idx][k] < dist[k] ) {
                dist[k] = min.weight + data[min.idx][k];
                path[k] = min.idx;
            }
        }
    }

    return [dist, path];
}
var data = [
    [0, 9, 2, Infinity, 6],
    [9, 0, 3, Infinity, Infinity],
    [2, 3, 0, 5, Infinity],
    [Infinity, Infinity, 5, 0, 1],
    [6, Infinity, Infinity, 1, 0]
];
console.log( dijkstra(data, 1) );

floyd求多源最短路径算法，任意两点最短距离

function floyd(data) {
    //初始化floyd算法的两个矩阵 
    var D = [], P = [];
    for(var i = 0; i < data.length; i++){
        D[i] = [];
        P[i] = [];
        for(var j = 0; j < data.length; j++){
            D[i][j] = data[i][j];
            P[i][j] = -1;
        }
    }

    //k为中间点 
    for(k = 0; k < data.length; k++){
        //i为起点 
        for(i = 0 ; i < data.length; i++){
            //j为终点 
            for(j =0; j < data.length; j++){
                if( D[i][k] + D[k][j] < D[i][j] ){
                    D[i][j] = D[i][k] + D[k][j];//更新最小路径 
                    P[i][j] = k;//更新最小路径中间顶点 
                }
            }
        }
    }

    console.log(D, P);
}
var data = [
    [0, 9, 2, Infinity, 6],
    [9, 0, 3, Infinity, Infinity],
    [2, 3, 0, 5, Infinity],
    [Infinity, Infinity, 5, 0, 1],
    [6, Infinity, Infinity, 1, 0]
];
floyd(data);
// 0 => [0, 5, 2, 7, 6]
// 1 => [5, 0, 3, 8, 9]
// 2 => [2, 3, 0, 5, 6]
// 3 => [7, 8, 5, 0, 1]
// 4 => [6, 9, 6, 1, 0]