Shortest-path problem: Dijkstra's algorithm
The algorithm of Dijkstra is used to compute the shortest path from a selected
node to all other nodes in a directed graph.
The graph may be constructed with the help of the graph
editor.
During the solution process the nodes for which the shortest distance is known
are marked yellow.
Symbols:
| i,j,h |
index of nodes |
| N-i |
node ii |
| c(i,j) |
distance from
node i to node j |
| MK |
sets of tagged
nodes |
| disctance(i)
|
shortest distance
from selected starting node to node i |
| predecessor(i) |
direct predecessor
of node i on the shortest path from the selected starting node to node i |
Literature:
- Domschke/Drexl (2005)
|
