Dijkstras 最短路径算法
在继续之前，建议你简要介绍一下 Adjacency Matrix 和 BFS
Dijkstra 算法被称为单源最短路径算法。它用于查找图中节点之间的最短路径，其可以表示例如道路网络。它由 Edsger W. Dijkstra于 1956 年构思，三年后出版。
我们可以使用广度优先搜索（BFS）搜索算法找到最短路径。该算法工作正常，但问题是，它假设遍历每条路径的成本相同，这意味着每条边的成本是相同的。Dijkstra 算法帮助我们找到每条路径成本不同的最短路径。
首先我们将看到，如何修改 BFS 以编写 Dijkstra 算法，然后我们将添加优先级队列以使其成为完整的 Dijkstra 算法。
假设每个节点与源的距离保持在 d [] 数组中。如同， d [3] 表示 d [3] 时间从源到达节点 3 。如果我们不知道距离，我们将在 d [3]中存储无穷大。另外，让 [u] [v] 代表 uv 的成本。这意味着从 u 节点到 v 节点需要花费[u] [v] 。 ** **** **** **** **** **** ****
我们需要了解 Edge Relaxation。比方说，从你的房子，即源头，到 A 的位置需要 10 分钟。而且要花 B 分钟需要 25 分钟。我们有， **** ** ****
d[A] = 10
d[B] = 25
现在让我们说从 A 地到 B 处需要 7 分钟，这意味着： **** ****
cost[A][B] = 7
然后，我们可以去放置B从源通过进入放置A从源，然后从一个地方A，要去的地方B，这将需要 10 + 7 = 17 分钟，而不是 25 分钟。所以，
d[A] + cost[A][B] < d[B]
然后我们更新，
d[B] = d[A] + cost[A][B]
这叫做放松。我们将从节点 u 到节点 v ，如果 **d [u] + cost [u] [v] <d [v]，**那么我们将更新 d [v] = d [u] + cost [u] [v] 。
在 BFS 中，我们不需要两次访问任何节点。我们只检查了是否访问过某个节点。如果没有访问它，我们将节点推入队列，将其标记为已访问并将距离增加 1.在 Dijkstra 中，我们可以推送队列中的节点，而不是使用访问更新它，我们放松或更新新边缘。我们来看一个例子：
我们假设，节点 1 是源。然后，
d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)
我们将 d [2]，d [3] 和 d [4]设置为*无穷大，*因为我们还不知道距离。而源的距离当然是 0 。现在，我们从源代码转到其他节点，如果我们可以更新它们，那么我们将它们推入队列中。比方说，我们将遍历边缘 1-2 。当 d [1] + 2 <d [2]时， d [2] = 2 。类似地，我们将遍历边缘 1-3 ，这使得 d [3] = 5 。
我们可以清楚地看到 5 不是我们可以跨越到节点 3 的最短距离。因此，像 BFS 一样只遍历一个节点在这里不起作用。如果我们使用边缘 2-3 从节点 2 到节点 3 ，我们可以更新 d [3] = d [2] + 1 = 3 。所以我们可以看到一个节点可以多次更新。你问多少次？节点可以更新的最大次数是节点的度数。 **** ****
让我们看一下多次访问任何节点的伪代码。我们将简单地修改 BFS：
procedure BFSmodified(G, source):
Q = queue()
distance[] = infinity
Q.enqueue(source)
distance[source]=0
while Q is not empty
u <- Q.pop()
for all edges from u to v in G.adjacentEdges(v) do
if distance[u] + cost[u][v] < distance[v]
distance[v] = distance[u] + cost[u][v]
end if
end for
end while
Return distance
这可用于从源中查找所有节点的最短路径。这段代码的复杂性不太好。这就是原因，
在 BFS 中，当我们从节点 1 到所有其他节点时，我们遵循先到先服务方法。例如，我们在处理节点 2 之前从源到节点 3 。如果我们从源转到节点 3 ，我们将节点 4 更新为 5 + 3 = 8 。当我们再次从节点 2 更新节点 3 时，我们需要再次将节点 4 更新为 3 + 3 = 6 ！ 因此节点 4 更新两次。 **** **** **** **** **** **** **** **** **** **** ****
Dijkstra 建议，如果我们先更新最近的节点，而不是先到先服务方法，那么它将需要更少的更新。如果我们之前处理过节点 2 ，那么节点 3 之前就已经更新，并且在相应地更新节点 4 之后，我们很容易得到最短的距离！ 我们的想法是从最靠近源的队列中选择节点。所以我们将在这里使用 Priority Queue ，这样当我们弹出队列时，它将为我们带来离源最近的节点 u 。它会怎么做？它会用它来检查 d [u] 的值。 **** ****
我们来看看伪代码：
procedure dijkstra(G, source):
Q = priority_queue()
distance[] = infinity
Q.enqueue(source)
distance[source] = 0
while Q is not empty
u <- nodes in Q with minimum distance[]
remove u from the Q
for all edges from u to v in G.adjacentEdges(v) do
if distance[u] + cost[u][v] < distance[v]
distance[v] = distance[u] + cost[u][v]
Q.enqueue(v)
end if
end for
end while
Return distance
伪代码返回所有其他节点与源的距离。如果我们想知道单个节点 v 的距离，我们可以简单地在从队列中弹出 v 时返回该值。
现在，Dijkstra 算法在出现负边缘时是否有效？如果存在负循环，则会出现无限循环，因为它会每次都降低成本。即使存在负边缘，Dijkstra 也无法工作，除非我们在弹出目标后立即返回。但是，它不会是 Dijkstra 算法。我们需要 Bellman-Ford 算法来处理负边缘/周期。
复杂：
BFS 的复杂度为 O（log（V + E）） ，其中 V 是节点数， E 是边数。对于 Dijkstra，复杂性类似，但优先级队列的排序需要 O(logV) 。总复杂度为： O（Vlog(V)+ E）
下面是使用邻接矩阵求解 Dijkstra 最短路径算法的 Java 示例
import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestPath
{
static final int V=9;
int minDistance(int dist[], Boolean sptSet[])
{
int min = Integer.MAX_VALUE, min_index=-1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
void printSolution(int dist[], int n)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i+" \t\t "+dist[i]);
}
void dijkstra(int graph[][], int src)
{
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
public static void main (String[] args)
{
int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}
该计划的预期产出是
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14