graph = {} # Задаём граф и вершину, от которой надо определить расстояния. for v1, v2, d in (('x1', 'x2', 3), ('x1', 'x4', 5), ('x2', 'x4', 2), ('x2', 'x7', 7), ('x3', 'x2', 3), ('x3', 'x6', 9), ('x4', 'x5', 1), ('x4', 'x6', 5), ('x5', 'x6', 8), ('x5', 'x7', 6), ('x6', 'x7', 10), ('x7', 'x3', 4), ('x7', 'x8', 4), ('x8', 'x6', 12)): assert d >= 0 # Все расстояния неотрицательны. graph.setdefault(v1, {}) graph.setdefault(v2, {}) assert v2 not in graph[v1] # Нельзя расстояние между двумя вершинами вводить дважды. graph[v1][v2] = d print graph def Dijkstra(graph, v0): distance = dict.fromkeys(graph, float('inf')) # Определяем словарь вершин с расстояниями до заданной равными бесконечности. distance[v0] = 0 # Задаём расстояние от заданной вершины до самой себя равным 0. print v0, distance vertex = set(graph) # Определяем множество вершин, для которых будем затем в цикле высчитывать расстояния. while vertex: # Пока есть необработанные вершины, продолжаем цикл. v1 = min(vertex, key=distance.get) # Определяем среди необработанных вершин, вершину с минимальным расстоянием до заданной. vertex.remove(v1) # Сейчас от неё будет вычислены расстояния до соседних и поэтому её можно удалить из множества необработанных вершин. for v, d in graph[v1].items(): # От выбранной вершины, для всех расстояний, если новое расстояние короч чем чем старое, то заносим новое. distance[v] = min(distance[v], distance[v1] + d) print v1, distance return distance # Возвращаем решение в виде словаря расстояний от заданной вершины. print Dijkstra(graph, 'x1')