#!/usr/bin/python2.7
# -*- coding: utf-8 -*-
# описываем что может каждая точка из графа в вики http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
graph = [
         [1 , 2 , 7],
         [1 , 3 , 9],
         [1 , 6 , 14],
         [2 , 3 , 10],
         [2 , 4 , 15],
         [3 , 4 , 11],
         [3 , 6 , 2],
         [4 , 5 , 6],
         [5 , 6 , 9]
         ]
# поехали ))
def algo_deistra(gr):
    all_data = {}
    rasst = {}
    for x1 , x2 , x3 in gr :
        # пасем все вершины
        if x1 not in all_data.keys() :
            all_data[x1] = {}
        if x2 not in all_data.keys() :
            all_data[x2] = {}
        # дополняем нехватающие данные (например соединения 6-й точки) + генерим словарь чего с чем контактирует
        if x2 not in all_data[x1].keys():
            all_data[x1][x2] = x3
        if x1 not in all_data[x2].keys() :
            all_data[x2][x1] = x3
    # запиливаем стартовые значения
    points = all_data.keys()
    for x in points:
        if x != 1 : rasst[x] = 'N/A'
        else : rasst[x] = 0
    # собсна сам поиск
    while points:
        current = min(points, key=rasst.get)
        print 'тестирую точку № %i , минимальное расстояние до нее : %s' % (current , rasst.get(current) )
        points.remove(current)
        for var, leng in all_data[current].items():
            rasst[var] = min(rasst[var], rasst[current] + leng)
    # вернем все результаты пачкой
    return rasst
print algo_deistra(graph)