## 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)

```