Структуры данных и модели вычислений
Нахождение кратчайших путей в графе
Входные данные:
- Граф со взвешенными ребрами (под весами можно понимать длины ребер, если речь идет о геометрическом графе, или любые другие числовые характеристики ребер). Пусть — вес ребра ().
- Стартовая вершина (вершина, от которой вычисляются расстояния до всех остальных вершин).
Выходные данные:
- Массив , — кратчайшее расстояние от вершины до вершины ).
- Массив , — предпоследняя вершина в кратчайшем пути из вершины
в вершину ).
Приводимый ниже алгоритм Дейкстры корректно решает задачу для графов с неотрицательными весами вершин. Если же в графе есть ребра с отрицательными весами, но нет циклов с отрицательным суммарным весом, то для решения задачи можно использовать алгоритм Форда, Беллмана.
