Python Tutorial

Monday, October 19, 2015

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]

Saturday, October 17, 2015

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)