Поиск кратчайших путей в графе

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Задача поиска кратчайших путей в графе (Shortest Path Problem), заключается в следующем:

Заданы n вершин графа (узлов сети) \(v_1,v_2,\ldots,v_n\) и целые длины дуг \(d_{ij} \equiv d(v_i,v_j)\) между ними. Чему равна наименьшая возможная длина пути, ведущего из v1 в vk, для всех \(k \in (2 \ldots n)\)?

Если длины дуг неотрицательны, то можно использовать алгоритм Дейкстры, если есть отрицательные длины, но нет циклов отрицательного веса (если такие циклы есть — то оптимального решения очевидно не существует), то можно использовать алгоритм Флойда-Уоршолла.
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.