Структуры данных и модели вычислений



         

Нахождение кратчайших путей в графе


Входные данные:

  • Граф со взвешенными ребрами (под весами можно понимать длины ребер, если речь идет о геометрическом графе, или любые другие числовые характеристики ребер). Пусть — вес ребра ().
  • Стартовая вершина (вершина, от которой вычисляются расстояния до всех остальных вершин).

Выходные данные:

  • Массив , — кратчайшее расстояние от вершины до вершины ).
  • Массив , — предпоследняя вершина в кратчайшем пути из вершины

    в вершину ).

Приводимый ниже алгоритм Дейкстры корректно решает задачу для графов с неотрицательными весами вершин. Если же в графе есть ребра с отрицательными весами, но нет циклов с отрицательным суммарным весом, то для решения задачи можно использовать алгоритм Форда, Беллмана.




Содержание  Назад  Вперед