SOURCE

/**
 * Dijkstra算法
 * 
 * @author wupanpan@baidu.com
 * @date 2014-03-26
 */

/**
 * @const
 */
var INF = Infinity;

/**
 * @param {number} sourceV 源点的索引，从0开始
 * @param {Array} adjMatrix 图的邻接矩阵，是一个二维数组
 */

function dijkstra(sourceV, adjMatrix) {
    var set = [],
        path = [],
        
        dist = [];
        distCopy = [],
        vertexNum = adjMatrix.length;

    var temp, u,
        count = 0;

    // 初始化
    for (var i = 0; i < vertexNum; i++) {
        distCopy[i] = dist[i] = INF;
        set[i] = false;
    }
    distCopy[sourceV] = dist[sourceV] = 0;

    while (count < vertexNum) {
        u = distCopy.indexOf(Math.min.apply(Math, distCopy));
        set[u] = true;
        distCopy[u] = INF;

        for (var i = 0; i < vertexNum; i++) {
            if (!set[i] && ((temp = dist[u] + adjMatrix[u][i]) < dist[i])) {
                distCopy[i] = dist[i] = temp;
                path[i] = u;
            }
        }
        count++;
    }

    return {
        path: path,
        dist: dist
    };1
}

/**
 * @param {number} v 源点索引, 从0开始
 * @param {number} d 非源点索引, 从0开始
 * @param {Array} adjMatrix 图的邻接矩阵，是一个二维数组
 */
function searchPath(v, d, adjMatrix) {
    var graph = dijkstra(v, adjMatrix),
        path = graph.path,
        dist = graph.dist;

    var prev = path[d],
        queue = [],
        str = '';
    
    queue.push(d);
    while(prev != v) {
        queue.push(prev);
        prev = path[prev];
    }
    queue.push(v);

    for (var j = queue.length - 1; j >= 0; j--) {
        str += queue.pop() + ' -> ';
    }
    console.log(str);
}


/**
 * 测试数据
 */
var adjM = [
    [0, 4, 2, INF, INF, INF],
    [4, 0, 1, 5, INF, INF],
    [2, 1, 0, 8, 10, INF],
    [INF, 5, 8, 0, 2, 6],
    [INF, INF, 10, 2, 0, 3],
    [INF, INF, INF, 6, 3, 0]
];
// var adjM = [
//     [0, 10, INF, 30, 100],
//     [10, 0, 50, INF, INF],
//     [INF, 50, 0, 20, 10],
//     [30, INF, 20, 0, 60],
//     [100, INF, 10, 60, 0]
// ];

searchPath(0, adjM.length - 1, adjM);