Задача о кратчайшем пути и алгоритм Дейкстры ее решения
Пусть задан орграф G(V, E), каждой дуге Определение. Длиной пути называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути ставится так. Вариант 1. Найти длины кратчайших путей (путей минимальной длины) и сами пути от фиксированной вершины s до всех остальных вершин графа. Вариант 2. Найти длины кратчайших путей и сами пути между всеми парами вершин данного графа. Если в графе имеются дуги отрицательной длины, задача может не иметь решений (потеряет смысл). Это происходит из-за того, что в графе может присутствовать контур отрицательной длины. Наличие контуров отрицательной длины означает, что длину пути можно сделать равной Заметим, что если кратчайший путь существует, то любой его подпуть – это тоже кратчайший путь между соответствующими вершинами.
|
которого поставлено в соответствие число 
, называемое длиной дуги.
. А если контуров отрицательной длины нет, то кратчайшие пути существуют и любой кратчайший путь – это простая цепь.
