Вычисление кратчайшего пути с помощью алгоритма дейкстры.

Необходимо пройти все вершины графа.

С помощью алгоритма дейкстры, я могу найти только минимальное расстояние от одного города до всех остальных.

Как узнать, через какие вершины проходит этот минимальный путь?
Далее я хочу проложить маршрут через все точки. Для этого, допустим, я вычислил минимальные расстояния от каждого города, до любого другого. Т. е. получилась матраца расстояний. 2. Как с помощью этой матрицы проложить кратчайший маршрут?