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

Z3JhcGggPSB7fSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjINCX0LDQtNCw0ZHQvCDQs9GA0LDRhCDQuCDQstC10YDRiNC40L3Rgywg0L7RgiDQutC+0YLQvtGA0L7QuSDQvdCw0LTQviDQvtC/0YDQtdC00LXQu9C40YLRjCDRgNCw0YHRgdGC0L7Rj9C90LjRjy4gCmZvciB2MSwgdjIsIGQgaW4gKCgneDEnLCAneDInLCAzKSwgIAogICAgICAgICAgICAgICAgICAoJ3gxJywgJ3g0JywgNSksCiAgICAgICAgICAgICAgICAgICgneDInLCAneDQnLCAyKSwKICAgICAgICAgICAgICAgICAgKCd4MicsICd4NycsIDcpLAogICAgICAgICAgICAgICAgICAoJ3gzJywgJ3gyJywgMyksCiAgICAgICAgICAgICAgICAgICgneDMnLCAneDYnLCA5KSwKICAgICAgICAgICAgICAgICAgKCd4NCcsICd4NScsIDEpLAogICAgICAgICAgICAgICAgICAoJ3g0JywgJ3g2JywgNSksCiAgICAgICAgICAgICAgICAgICgneDUnLCAneDYnLCA4KSwKICAgICAgICAgICAgICAgICAgKCd4NScsICd4NycsIDYpLAogICAgICAgICAgICAgICAgICAoJ3g2JywgJ3g3JywgMTApLAogICAgICAgICAgICAgICAgICAoJ3g3JywgJ3gzJywgNCksCiAgICAgICAgICAgICAgICAgICgneDcnLCAneDgnLCA0KSwKICAgICAgICAgICAgICAgICAgKCd4OCcsICd4NicsIDEyKSk6IAogIGFzc2VydCBkID49IDAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjINCS0YHQtSDRgNCw0YHRgdGC0L7Rj9C90LjRjyDQvdC10L7RgtGA0LjRhtCw0YLQtdC70YzQvdGLLiAKICBncmFwaC5zZXRkZWZhdWx0KHYxLCAge30pCiAgZ3JhcGguc2V0ZGVmYXVsdCh2MiwgIHt9KQogIGFzc2VydCB2MiBub3QgaW4gZ3JhcGhbdjFdICAgICAgICAgICAgICAgICAgICAjINCd0LXQu9GM0LfRjyDRgNCw0YHRgdGC0L7Rj9C90LjQtSDQvNC10LbQtNGDINC00LLRg9C80Y8g0LLQtdGA0YjQuNC90LDQvNC4INCy0LLQvtC00LjRgtGMINC00LLQsNC20LTRiy4gIAogIGdyYXBoW3YxXVt2Ml0gPSBkICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKCnByaW50IGdyYXBoCgpkZWYgRGlqa3N0cmEoZ3JhcGgsIHYwKToKICBkaXN0YW5jZSA9IGRpY3QuZnJvbWtleXMoZ3JhcGgsIGZsb2F0KCdpbmYnKSkgIyDQntC/0YDQtdC00LXQu9GP0LXQvCDRgdC70L7QstCw0YDRjCDQstC10YDRiNC40L0g0YEg0YDQsNGB0YHRgtC+0Y/QvdC40Y/QvNC4INC00L4g0LfQsNC00LDQvdC90L7QuSDRgNCw0LLQvdGL0LzQuCDQsdC10YHQutC+0L3QtdGH0L3QvtGB0YLQuC4KICBkaXN0YW5jZVt2MF0gPSAwICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyDQl9Cw0LTQsNGR0Lwg0YDQsNGB0YHRgtC+0Y/QvdC40LUg0L7RgiDQt9Cw0LTQsNC90L3QvtC5INCy0LXRgNGI0LjQvdGLINC00L4g0YHQsNC80L7QuSDRgdC10LHRjyDRgNCw0LLQvdGL0LwgMC4gICAgICAKICBwcmludCB2MCwgZGlzdGFuY2UKICB2ZXJ0ZXggPSBzZXQoZ3JhcGgpICAgICAgICAgICAgICAgICAgICAgICAgICAgIyDQntC/0YDQtdC00LXQu9GP0LXQvCDQvNC90L7QttC10YHRgtCy0L4g0LLQtdGA0YjQuNC9LCDQtNC70Y8g0LrQvtGC0L7RgNGL0YUg0LHRg9C00LXQvCDQt9Cw0YLQtdC8INCyINGG0LjQutC70LUg0LLRi9GB0YfQuNGC0YvQstCw0YLRjCDRgNCw0YHRgdGC0L7Rj9C90LjRjy4gICAKICB3aGlsZSB2ZXJ0ZXg6ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyDQn9C+0LrQsCDQtdGB0YLRjCDQvdC10L7QsdGA0LDQsdC+0YLQsNC90L3Ri9C1INCy0LXRgNGI0LjQvdGLLCDQv9GA0L7QtNC+0LvQttCw0LXQvCDRhtC40LrQuy4gCiAgICB2MSA9IG1pbih2ZXJ0ZXgsIGtleT1kaXN0YW5jZS5nZXQpICAgICAgICAgICMg0J7Qv9GA0LXQtNC10LvRj9C10Lwg0YHRgNC10LTQuCDQvdC10L7QsdGA0LDQsdC+0YLQsNC90L3Ri9GFINCy0LXRgNGI0LjQvSwg0LLQtdGA0YjQuNC90YMg0YEg0LzQuNC90LjQvNCw0LvRjNC90YvQvCDRgNCw0YHRgdGC0L7Rj9C90LjQtdC8INC00L4g0LfQsNC00LDQvdC90L7QuS4gCiAgICB2ZXJ0ZXgucmVtb3ZlKHYxKSAgICAgICAgICAgICAgICAgICAgICAgICAgICMg0KHQtdC50YfQsNGBINC+0YIg0L3QtdGRINCx0YPQtNC10YIg0LLRi9GH0LjRgdC70LXQvdGLINGA0LDRgdGB0YLQvtGP0L3QuNGPINC00L4g0YHQvtGB0LXQtNC90LjRhSDQuCDQv9C+0Y3RgtC+0LzRgyDQtdGRINC80L7QttC90L4g0YPQtNCw0LvQuNGC0Ywg0LjQtyDQvNC90L7QttC10YHRgtCy0LAg0L3QtdC+0LHRgNCw0LHQvtGC0LDQvdC90YvRhSDQstC10YDRiNC40L0uIAogICAgZm9yIHYsIGQgaW4gZ3JhcGhbdjFdLml0ZW1zKCk6ICAgICAgICAgICAgICAjINCe0YIg0LLRi9Cx0YDQsNC90L3QvtC5INCy0LXRgNGI0LjQvdGLLCDQtNC70Y8g0LLRgdC10YUg0YDQsNGB0YHRgtC+0Y/QvdC40LksINC10YHQu9C4INC90L7QstC+0LUg0YDQsNGB0YHRgtC+0Y/QvdC40LUg0LrQvtGA0L7RhyDRh9C10Lwg0YfQtdC8INGB0YLQsNGA0L7QtSwg0YLQviDQt9Cw0L3QvtGB0LjQvCDQvdC+0LLQvtC1LiAKICAgICAgZGlzdGFuY2Vbdl0gPSBtaW4oZGlzdGFuY2Vbdl0sIGRpc3RhbmNlW3YxXSArIGQpCiAgICBwcmludCB2MSwgZGlzdGFuY2UKICByZXR1cm4gZGlzdGFuY2UgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyDQktC+0LfQstGA0LDRidCw0LXQvCDRgNC10YjQtdC90LjQtSDQsiDQstC40LTQtSDRgdC70L7QstCw0YDRjyDRgNCw0YHRgdGC0L7Rj9C90LjQuSDQvtGCINC30LDQtNCw0L3QvdC+0Lkg0LLQtdGA0YjQuNC90YsuICAKICAgIApwcmludCBEaWprc3RyYShncmFwaCwgJ3gxJykK