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

Рассмотрим орграф G=(V,E), дугам которого предписаны веса. Это означает, что каждой дуге (u,v), принадлежащей множеству ребер Е поставлено в соответствие некоторое вещественное число a(u,v), называемое весом данной дуги.

Если дуга (u,v) не существует, то d(u,v)=∞

Если последовательность вершин V0, V1, V2, …, Vi определяет маршрут в графе G, то его длина определяется по формуле

d= a(V_i-1,V_i)

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами S и T, принадлежащих множеству V.

Длину такого пути будем обозначать d(S,T) и называть расстоянием от S до T.

Если не существует исходного пути из S в T, то d(S,T)= ∞

Контур – нетривиальный замкнутый маршрут, у которого все вершины различны (за исключением первой и последней).

(3)

Ex:

(1)

(3)

(-5)

(8)

(2)

(1)

Граф А

(4)

(3)

Матрица весов дуг графа А:

1 2 3 4 5