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

       

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


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

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

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

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

    в вершину ).

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



Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий