Python алг. Дейкстры

[Oinevle]

Есть алгоритм Декйстры, как его докрутить, чтобы он ещё и показывал сам минмальный путь от вершины до вершины? Например, минимальное расстояние: 10, путь x1,x2,x6,x8.

Билблиотеке не вариант, с ними уже и сам сделал.

Заранее спасибо.

http://ideone.com/kKAc2T

[Somebody]

Надо кроме массива расстояний для каждой вершины сохранять ещё и предыдущую вершину, тогда можно будет отследить путь, если начать с конечной вершины.