Algorithms/dijkstras.py at master · Manikumar1998/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys

def get_min(graph, keys, isvisited):
    minimum = sys.maxint
    min_index = None
    for i in xrange(len(keys)):
        if keys[i] < minimum and isvisited[i] == False:
            minimum = keys[i]
            min_index = i
    return min_index

def dijkstras(graph, N):
    keys = [sys.maxint for i in xrange(N)]
    parent = range(N)
    isvisited = [False for i in xrange(N)]

    keys[0] = 0
    n = N
    while(n):
        index = get_min(graph, keys, isvisited)
        isvisited[index] = True

        for i in xrange(len(graph)):
            if graph[index][i] != 0 and keys[index] + graph[index][i] < keys[i]:
                keys[i] = graph[index][i] + keys[index]
                parent[i] = index
        n -= 1
    print keys

if __name__ == '__main__':
    graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0]
          ];
    dijkstras(graph, len(graph))