Dijkstra算法

Dijkstra算法

Dijkstra算法求图中最短路径的一种算法,优点是其能找到所有最短路径,但是要求图中不能含有负权值的边。

算法描述

Dijkstra算法的思想是一种贪婪算法,初始化时根节点(root)被设置为distance = 0 并放在优先队列S中,其他节点被设置成distance = +inf 并放在等待队列V中。设descendent node是V的某一个节点,我们把从processed node到descendent node且中间只经过S中节点的路径叫做关键路径,采用数组dist记录路径长度,也就是说在算法中保证

distance.processed + edgeWeight.(processed,descendant) < distance.descendent

如果上式成立,那么将processed node设置成descendant node 的祖先节点(ancestor),遍历V集合中的所有节点,然后选取最优(最短路径)加入S集合中,然后重复上述过程,直到V集合为空。

/**
* Dijkstra's algorithm
* @param d matrix of legths, position [0 1] = 2 means that from node 0 leads an edge to node 1 of length 2
* @param from root node
* @return tree an ancestors (denotes path from the node to the root node)
*/
procedure int[] doDijkstra(d, from) {
//insert all nodes to the priority queue, node from has a distance 0, all others infinity
Q = InsertAllNodesToTheQueue(d, from)
CLOSED = {} //closed nodes - empty set
predecessors = new array[d.nodeCount] //array of ancestors

while !Q.isEmpty() do
node = Q.extractMin()
CLOSED.add(node) //close the node

//contract distances
for a in Adj(node) do //for all descendants
if !CLOSED.contains(a) //if the descendatn was not closed yet
//and his distance has decreased
if Q[node].distance + d[node][a] < Q[a].distance
//zmen prioritu (vzdalenost) uzlu
Q[a].distance = Q[node].distance + d[node][a]
//change its ancestor
predecessors[a] = node

return predecessors



/**
* Dijkstra's algorithm
* @param d matrix of lengths (Integer.MAX_VALUE if there is no edge between the nodes)
* @param from root node
* @return tree an ancestors (denotes path from the node to the root node)
*/
public static int[] doDijkstra(int[][] d, int from) {
Set<Integer> set = new HashSet<Integer>();
set.add(from);

boolean[] closed = new boolean[d.length];
int[] distances = new int[d.length];
for (int i = 0; i < d.length; i++) {
if (i != from) {
distances[i] = Integer.MAX_VALUE;
} else {
distances[i] = 0;
}
}


int[] predecessors = new int[d.length];
predecessors[from] = -1;

while (!set.isEmpty()) {
//find the nearest node
int minDistance = Integer.MAX_VALUE;
int node = -1;
for(Integer i : set){
if(distances[i] < minDistance){
minDistance = distances[i];
node = i;
}
}

set.remove(node);
closed[node] = true;

//contract the distances
for (int i = 0; i < d.length; i++) {
//edge exists
if (d[node][i] != Integer.MAX_VALUE) {
if (!closed[i]) {
//the path length decreased using the ancestor node
if (distances[node] + d[node][i] < distances[i]) {
distances[i] = distances[node] + d[node][i];
predecessors[i] = node;
set.add(i);
}
}
}
}
}
return predecessors;
}

图示

迭代 S descentdent node dist[A] dist[B] dist[C] dist[D]
初始 {S} - 20 10 max int 70
1 {S,B} B 20 10 40 70
2 {S,B,A} A 20 10 40 70
3 {S,B,A,C} C 20 10 40 70
4 {S,B,A,C,D} D 20 10 40 70