Dijkstra algorithm

Dijkstra algorithm is a single source shortest path algorithm. For a given source node in the graph, the algorithm finds the shortest path between that node and every other.

Here is the python implementation of Dijkstra algorithm

from heapq import heappush, heappop

# 0 index base dijkstra algorithm
def Dijkstra(graph, source):
    A = [None] * len(graph)
    queue = [(0, source)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # set -1 for unreachable           
    return [-1 if x is None else x for x in A] 

graph = {
  0: { 1:2, 2:4, 3:1 },
  1: { 2:1, 3:3 },
  2: { 4: 7},
  3: { 2: 2 },
  4: { 0:2, 3:3 }, 
  5: {}
}
source = 0

print Dijkstra(graph, source)

Output:

[0, 2, 3, 1, 10, -1]

python heapq/priority queue/Min heap

Python heapq provides implementation of the heap(min) queue algorithm, also known as the priority queue algorithm. Here's some example code.

from heapq import heappush, heappop

# priority queue normal
h = []
heappush(h, 5)
heappush(h, 1)
heappush(h, 3)

print heappop(h),"size",len(h)
print heappop(h),"size",len(h)
print heappop(h),"size",len(h)

# priority queue with tuple number and string
h = []
heappush(h, (5, "sample text"))
heappush(h, (1, "important text"))
heappush(h, (1, "a important text"))
heappush(h, (9, "un-important text"))

print heappop(h)
print heappop(h)

# priority queue with tuple number only 
h = []
heappush(h, (5, 3))
heappush(h, (7, 3))
heappush(h, (1, 3))
heappush(h, (1, 1))
heappush(h, (1, 2))
heappush(h, (3, 2))
heappush(h, (3, 1))

print heappop(h)
print heappop(h)
print heappop(h)

Output:

1 size 2
3 size 1
5 size 0
(1, 'a important text')
(1, 'important text')
(1, 1)
(1, 2)
(1, 3)