dijkstra.py

# coding: utf8
def dijkstra_shortest_path(graph, start, paths={}, visited=[]):
    if len(paths) == 0:
        paths[start] = {'dist': 0, 'parent': None} # инициализация начального пути
    # print "start V: %d, " % (start)
    for x in graph[start]:
        if (x not in visited and x != start):
            if (x not in paths.keys() or (graph[start][x] + paths[start]['dist']) < paths[x]['dist']):
                paths.setdefault(x, {'dist': 0, 'parent': None})
                paths[x]['dist'] = graph[start][x] + paths[start]['dist']
                paths[x]['parent'] = start

    visited.append(start)

    min_v = 0
    min_x = None
    for x in paths:
        # print "x: %d, p[x]: %d, mv %d" % (x, p[x], min_v)
        if (paths[x]['dist'] < min_v or min_v == 0) and x not in visited:
                min_x = x
                min_v = paths[x]['dist']

    if(len(visited) < len(graph) and min_x):
        return dijkstra_shortest_path(graph, min_x, paths, visited)
    else:
        return paths

if __name__ == '__main__':
    # инициализация графа с помощью словаря смежности
    a, b, c, d, e, f, g, h = range(8)
    N = [
        {b: 7, c: 9, f: 14},
        {a: 7, c: 10, d: 15},
        {a: 9, b: 10, d: 11, f: 2},
        {b: 15, c: 11, e: 6},
        {d: 6, f: 9},
        {a: 14, c: 2, e: 9},
        {h: 2},
        {g: 2},
    ]
    for i in range(1):
        print(dijkstra_shortest_path(N, a))