Algorithms For Dummies

  Reconnecting the Dots 

     195

When the distance recorded in the priority queue isn’t infinite, but it’s more than 

the distance that the algorithm has just calculated, it means that the algorithm 

has found a shortcut, a shorter way to reach that vertex from the starting point, 

and it stores the information in the priority queue. Of course, if the distance 

recorded in the priority queue is shorter than the one just evaluated by the algo-

rithm, the algorithm discards the information because the new route is longer. 

After updating all the distances to the neighboring vertexes, the algorithm deter-

mines whether it has reached the end vertex. If not, it picks the shortest edge 

present in the priority queue, visits it, and starts evaluating the distance to the 

new neighboring vertexes.

As the narrative of the algorithm explained, Dijikstra’s algorithm keeps a precise 

accounting of the cost to reach every vertex that it encounters, and it updates its 

information only when it finds a shorter way. The running complexity of the algo-

rithm in Big-O notation is O(E*log(V)), where E is the number of edges and V the 

number of vertexes in the graph. The following code shows how to implement 

Dijikstra’s algorithm using Python:

def dijkstra(graph, start, end):

    inf = float('inf')

    known = set()

    priority = priority_queue()

    path = {start: start}

    for vertex in graph:

        if vertex == start:

            priority.push(0, vertex)

        else:

            priority.push(inf, vertex)

    last = start

    while last != end:

        (weight, actual_node) = priority.pop()

        if actual_node not in known:

            for next_node in graph[actual_node]:

                upto_actual = priority.index[actual_node]

                upto_next = priority.index[next_node]

                to_next = upto_actual 

+ \

                graph[actual_node][next_node]

                if to_next < upto_next:

                    priority.push(to_next, next_node)

                    print("Found shortcut from %s to %s"

                          % (actual_node, next_node))

                    print ("\tTotal length up so far: %i"

---

196