Оптимизация в графах

[frankenstein]

Задача звучит так:
Представьте себя в большом городе. Вы хотите попасть из точки A в точку B. Для этого вы можете идти пешком или использовать метро. Перемещение с помощью метро быстрее, но входить в метро и выходить из него можно только на станциях. Чтобы сэкономить время, вы решили написать программу нахождения самого быстрого пути.
Дано:
Координаты точек A, B а также координаты станций метро, также заданы связи между ними (метро связаны прямыми путями).
Так же известно что скорость пешком равна $v_p$, а на метро $v_m$.
Требуется найти минимальное время за которое можно попасть из A в B.

Решение:
Я решил сделать так:
Построить неориентированный, сильно связный, взвшенный граф из точек A, B, и станций метро. Для всех ребер вычислить их вес(в контексте задачи это время за которое можно пройти это расстояние). Потом применить поиск в ширину и вычислить минимальное время.
Проблемы:
Не могу решить на какой базе построить граф, что лучше подойдет: матрица смежности, связные узлы или ...?
Нашел кое что по матрицам инцидентности, они вроде как раз подходят для представления графов со взвешенными ребрами.
Но не знаю как с ними работать.

А также, возможно, есть другое решение, более легкое.

[Null]

Я бы взял матрицу смежности. $a[i,j]$ Время движения между $i$ и $j$ вершиной. И использовал алгоритм Дейкстры.

[frankenstein]

Я пользовался алгоритмом Дейкстры только на графах, представленных на основе связных списков.
Можете как-то в общем описать как будет работать поиск в ширину на матрицах смежности, или дать
соответствующие ссылки?

[Null]

Поиск в ширину тут не при чем.