About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp

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