Dijkstra's algorithm
A computer scientest named Edsger W. Dijkstra (pronounced "DIKE-stra")
proposed in 1959 this algorithm for finding a path of least total weight
between two vertices in a weighted graph:
- Label the starting vertex with distance 0 and all other vertices with a distance larger than the length of any path.
-
Repeat until the ending vertex is red:
- Among the untried black vertices, choose one with the smallest distance, say d.
- Color the chosen vertex red.
- For each neighboring black vertex, along edge of weight w:
- If its distance is more than d + w:
- Change its
distance to d + w.
- Color the connecting edge red.
- Recolor any other incident edge black.
Finished. The shortest path is in red.
The algorithm is now displayed on the StepperTM.
Copyright © 1999-2000 SciMathMN