扩展Dijkstra算法：查找所有最短路径的实现指南

if shortest_distance + edge_distance < shortest_distances[vertex_index]:

if shortest_distance + edge_distance <= shortest_distances[vertex_index]:

const NO_PARENT = -1; // 实际上，我们使用空数组表示无父节点

function dijkstra(adjacencyMatrix, startVertex) {
    const nVertices = adjacencyMatrix[0].length;

    // shortestDistances[i] 存储从 startVertex 到 i 的最短距离
    const shortestDistances = new Array(nVertices).fill(Number.MAX_SAFE_INTEGER);

    // added[i] 为 true 表示顶点 i 已经包含在最短路径树中
    const added = new Array(nVertices).fill(false);

    // 初始化所有距离为无限大，added[] 为 false
    for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
        shortestDistances[vertexIndex] = Number.MAX_SAFE_INTEGER;
        added[vertexIndex] = false;
    }

    // 源顶点到自身的距离为 0
    shortestDistances[startVertex] = 0;

    // parents 数组存储最短路径树，每个元素是一个父节点数组
    // 注意：这里不能直接fill([])，因为会引用同一个数组。
    // 应该在需要时为每个节点初始化一个新数组。
    const parents = new Array(nVertices);
    for (let i = 0; i < nVertices; i++) {
        parents[i] = [];
    }

    // 起始顶点没有父节点
    parents[startVertex] = [];

    // 寻找所有顶点的最短路径
    for (let i = 1; i < nVertices; i++) {
        // 从未处理的顶点集中选择距离最小的顶点
        let nearestVertex = -1;
        let shortestDistance = Number.MAX_SAFE_INTEGER;

        for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            if (!added[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance) {
                nearestVertex = vertexIndex;
                shortestDistance = shortestDistances[vertexIndex];
            }
        }

        // 标记选中的顶点为已处理
        added[nearestVertex] = true;

        // 更新相邻顶点的距离值
        for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            const edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];

            // 仅当存在边且通过 nearestVertex 能够找到更短或等长的路径时更新
            if (edgeDistance > 0 && shortestDistance + edgeDistance <= shortestDistances[vertexIndex]) {
                // 如果是更短的路径，清空旧的父节点，并添加新的父节点
                if (shortestDistance + edgeDistance < shortestDistances[vertexIndex]) {
                    parents[vertexIndex] = []; // 重置父节点列表
                }
                // 如果是等长的路径，或者清空后添加，将 nearestVertex 加入父节点列表
                // 确保不重复添加父节点
                if (parents[vertexIndex].indexOf(nearestVertex) === -1) {
                    parents[vertexIndex].push(nearestVertex);
                }
                // 更新最短距离
                shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
            }
        }
    }

    printSolution(startVertex, shortestDistances, parents);
}

// 辅助函数：打印构建的距离数组和所有最短路径
function printSolution(startVertex, distances, parents) {
    const nVertices = distances.length;
    document.write("<h2>所有最短路径</h2>");
    document.write("<table border='1'><tr><th>起点 -> 终点</th><th>距离</th><th>路径</th></tr>");

    for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
        if (vertexIndex !== startVertex) {
            document.write(`<tr><td>${startVertex} -> ${vertexIndex}</td><td>${distances[vertexIndex]}</td><td>`);
            let results = printPath(vertexIndex, parents);
            for (let r of results) {
                document.write(`${r}<br>`);
            }
            document.write(`</td></tr>`);
        }
    }
    document.write("</table>");
}

// 递归函数：从源到 currentVertex 打印所有最短路径
function printPath(currentVertex, parents, pathText = "") {
    let results = [];
    // 构建当前路径文本
    if (pathText === "") {
        pathText = String(currentVertex);
    } else {
        pathText = currentVertex + " -> " + pathText;
    }

    // 如果当前节点有父节点，则递归遍历所有父节点
    if (parents[currentVertex] && parents[currentVertex].length > 0) {
        for (let p of parents[currentVertex]) {
            let innerResults = printPath(p, parents, pathText);
            for (let ir of innerResults) {
                results.push(ir);
            }
        }
    } else {
        // 如果没有父节点（即到达源节点），则当前路径完成
        results.push(pathText);
    }
    return results;
}

// 驱动代码
const adjacencyMatrix = [
    [0, 1, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
];

document.write("<h3>测试图：</h3>");
document.write("<pre class="brush:php;toolbar:false;">");
document.write("0 -> 1 (距离 1)\n");
document.write("0 -> 2 (距离 1)\n");
document.write("1 -> 3 (距离 1)\n");
document.write("2 -> 3 (距离 1)\n");
document.write("

0 -> 1 (距离 1)
0 -> 2 (距离 1)
1 -> 3 (距离 1)
2 -> 3 (距离 1)