Shortest path

Find the path with the samllest total weight.

Dijkstra's Algorithm

an iterative algorithm that provides us with the shortest path from one particular starting node to all other nodes in the graph.

Add a dist instance variable in the Vertex class. It contains the current total weight of the smallest weight path from the start to the vertex.

It will iterates once for every vertext in the graph, but the order is controlled by a priority queue. order depends on dist.

When a vertex is first created dist is set to a very large number.

def dijkstra(aGraph, start):
    pq = PriorityQueue()
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(), v) for v in aGraph])
    while pq:
        curr_vert = pq.delMin()
        for next_vert in curr_vert.getConnections():
            new_dist = curr_vert.getDistance() + curr_vert.getWeight(new_vert)
            if new_dist < next_vert.getDistance():
                next_vert.setDistance(new_dist)
                next_vert.setPred(curr_vert)
                pq.decreaseKey(next_vert, new_dist) # update value in priority queue

Notes

Dijkstra works only when the weights are all positives.

Analysis

O(VlogV + ElogV) = O((V+E)logV)