本文深入探讨了如何修改标准Dijkstra算法，使其不仅能找到单个最短路径，还能识别并输出图中所有长度相同的最短路径。通过调整距离更新条件和父母节点跟踪机制，我们将实现一个能够处理非唯一最短路径场景的Dijkstra变体，并提供具体的JavaScript代码示例和注意事项。
引言：Dijkstra算法与非唯一最短路径问题
Dijkstra算法是解决单源最短路径问题的经典算法，它通常用于在加权图中找到从起始节点到所有其他节点的最短路径。然而，在标准实现中，当存在多条路径具有相同的最小长度时，Dijkstra算法通常只会记录并输出其中的一条。在某些应用场景中，我们需要获取所有这些等长的最短路径，这要求我们对算法进行修改。
核心挑战在于如何有效地跟踪和存储每个节点的多个“父节点”，即那些能通过最短路径到达当前节点的上一个节点。传统的Dijkstra算法为每个节点只保留一个父节点，这导致了非唯一最短路径信息的丢失。
核心修改策略：支持多父节点与距离更新
要使Dijkstra算法能够处理非唯一最短路径，需要对两个关键部分进行修改：
- 距离更新条件：从严格小于 (<) 变为小于等于 (<=)。
- 父节点跟踪机制：为每个节点维护一个父节点集合（例如，一个数组），而不是单个父节点。
1. 调整距离更新条件
标准Dijkstra算法在更新节点距离时，会检查通过当前处理节点到达邻居节点的距离是否严格小于已知的最短距离。如果存在等长的路径，它会忽略新的路径。为了捕获所有最短路径，我们需要将条件从：
if shortest_distance + edge_distance < shortest_distances[vertex_index]:
修改为：
if shortest_distance + edge_distance <= shortest_distances[vertex_index]:
这意味着，如果发现一条与已知最短路径等长的新路径，我们也应该考虑它。
2. 处理父节点集合
当通过当前节点 nearestVertex 到达邻居节点 vertex_index 时，根据新的距离 shortest_distance + edge_distance 与 shortest_distances[vertex_index] 的关系，我们需要采取不同的父节点更新策略：
情况一：发现更短的路径 如果 shortest_distance + edge_distance < shortest_distances[vertex_index]，这意味着我们找到了一条比之前任何路径都更短的新路径。此时，需要清空 vertex_index 的所有现有父节点，并将 nearestVertex 设置为其唯一的父节点。同时，更新 shortest_distances[vertex_index] 为新的最短距离。
情况二：发现等长的路径 如果 shortest_distance + edge_distance == shortest_distances[vertex_index]，这意味着我们找到了一条与已知最短路径等长的新路径。在这种情况下，不应清空父节点列表，而应该将 nearestVertex 添加到 vertex_index 的父节点集合中（如果它尚未存在）。
通过这种方式，parents 数组的每个元素将不再是一个简单的整数，而是一个包含零个或多个父节点索引的数组。
示例代码：JavaScript 实现
以下是一个修改后的Dijkstra算法JavaScript实现，它展示了如何处理多重最短路径：
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>");
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("</pre>");
document.write("<p>从 0 到 3 有两条最短路径，长度均为 2：</p>");
document.write("<p>1. 0 -> 1 -> 3</p>");
document.write("<p>2. 0 -> 2 -> 3</p>");
dijkstra(adjacencyMatrix, 0);代码解析：
- parents 数组初始化：parents 现在是一个二维数组，parents[i] 存储了所有能够通过最短路径到达节点 i 的前一个节点。
-
距离更新逻辑：在 dijkstra 函数内部，if (edgeDistance > 0 && shortestDistance + edgeDistance <= shortestDistances[vertex_index]) 这一行是关键。
- 如果 shortestDistance + edgeDistance < shortestDistances[vertex_index]，说明找到了一条更短的路径，此时 parents[vertex_index] 会被清空，然后添加 nearestVertex。
- 如果 shortestDistance + edgeDistance == shortestDistances[vertex_index]，说明找到了一条等长的路径，此时 nearestVertex 会被直接添加到 parents[vertex_index] 中（确保不重复）。
- printPath 函数：这是一个递归函数，用于遍历 parents 数组并重建所有可能的路径。它从目标节点开始，向上追溯所有父节点，直到到达源节点，从而生成完整的路径字符串。由于一个节点可能有多个父节点，这个函数会递归地探索所有分支。
测试图示例：
提供的邻接矩阵表示了一个简单的图：
0 -> 1 (距离 1) 0 -> 2 (距离 1) 1 -> 3 (距离 1) 2 -> 3 (距离 1)
从节点 0 到节点 3，存在两条最短路径，长度均为 2：
- 0 -> 1 -> 3
- 0 -> 2 -> 3
修改后的算法将能够识别并打印这两条路径。
注意事项与总结
- 递归深度限制：printPath 函数是递归的。在节点数量非常多、或者最短路径非常长且分支非常多的复杂图中，可能会遇到JavaScript的默认递归深度限制。对于这类情况，可能需要考虑使用迭代方式来打印路径，或者优化路径存储结构。
- 性能开销：存储多个父节点会增加内存使用量。同时，printPath 函数在有大量等长路径时，其计算复杂度会显著增加，因为它需要遍历所有可能的路径组合。
- 图的类型：此修改适用于无负权边的图，因为Dijkstra算法本身不处理负权边。
- 彻底测试：在实际应用中，务必对修改后的算法进行彻底测试，尤其是在边缘情况和复杂图结构下，以确保其正确性和鲁棒性。
通过上述修改，Dijkstra算法可以扩展其功能，不仅提供最短路径的长度，还能提供所有达到该长度的路径详情，这对于需要路径多样性分析的场景非常有用。
