## Shortest Routes

__Dijkstra’s Algorithm__- Label the start vertex with permanent distance label 0 and order label 1.
- Assign temporary labels (working values) to all the vertices that can be reached directly from the start.
- Select the vertex with the smallest working value and make its label permanent. Add the correct order label.
- Put working values on each vertex that can be reached directly from the vertex you have just made permanent. The working value must be equal to the sum of the permanent label and the direct distance from it. If there is an existing temporary label at a vertex, it should be replaced only if the new sum is smaller (by crossing out the old one – while keeping it visible).
- Select the vertex with the smallest working value and make its label permanent. Add the correct order label.
- Repeat until the finishing vertex has a permanent label.
- To find the shortest path(s), trace back from the end vertex to the start vertex – the path such that the difference in permanent labels equals the weight of the connecting edge.
- Write the route forwards and state the length.

**Example:**

A limitation of Dijkstra’s is that it does not work when there are negative weights.