Файл: Embedded Robotics (Thomas Braunl, 2 ed, 2006).pdf

Dijkstra’s Algorithm

Algorithm Start “ready set” with start node. In loop select node with shortest distance in every step, then compute distances to all of its neighbors and store path predecessors. Add current node to “ready set”; loop finishes when all nodes are included.

1. Init

Set start distance to 0, dist[s]=0, others to infinite: dist[i]=f (for izs), Set Ready = { } .

2. Loop until all nodes are in Ready

Select node n with shortest known distance that is not in Ready set Ready = Ready + {n} .

FOR each neighbor node m of n

IF dist[n]+edge(n,m) < dist[m] /* shorter path found */ THEN { dist[m] = dist[n]+edge(n,m);

pre[m] = n;

}

DE

DE

Figure 14.8: Dijkstra’s algorithm step 0 and 1

207

Dijkstra’s Algorithm

Example Consider the nodes and distances in Figure 14.8. On the left hand side is the distance graph, on the right-hand side is the table with the shortest distances found so far and the immediate path predecessors that lead to this distance.

In the beginning (initialization step), we only know that start node S is reachable with distance 0 (by definition). The distances to all other nodes are infinite and we do not have a path predecessor recorded yet. Proceeding from step 0 to step 1, we have to select the node with the shortest distance from all nodes that are not yet included in the Ready set. Since Ready is still empty, we have to look at all nodes. Clearly S has the shortest distance (0), while all other nodes still have an infinite distance.

For step 1, Figure 14.8 bottom, S is now included into the Ready set and the distances and path predecessors (equal to S) for all its neighbors are being updated. Since S is neighbor to nodes a, c, and d, the distances for these three nodes are being updated and their path predecessor is being set to S.

When moving to step 2, we have to select the node with the shortest path among a, b, c, d, as S is already in the Ready set. Among these, node c has the shortest path (5). The table is updated for all neighbors of c, which are S, a, b, and d. As shown in Figure 14.9, new shorter distances are found for a, b, and d, each entering c as their immediate path predecessor.

In the following steps 3 through 5, the algorithm’s loop is repeated, until finally, all nodes are included in the Ready set and the algorithm terminates. The table now contains the shortest path from the start node to each of the other nodes, as well as the path predecessor for each node, allowing us to reconstruct the shortest path.

Figure 14.10: Determine shortest path

Figure 14.10 shows how to construct the shortest path from each node’s predecessor. For finding the shortest path between S and b, we already know the shortest distance (9), but we have to reconstruct the shortest path backwards from b, by following the predecessors:

pre[b]=a, pre[a]=c, pre[c]=S

Therefore, the shortest path is: S o c o a o b

209