Орсети, кратчайшие пути, алгоритм Дейкстры.

Ориентированная сеть (орсеть) – связный граф с положительными весами на дугах.

Если в сети существует вершина, из которой достижимы все остальные вершины, то сеть называется корневой, а вершина – корнем.

Вес сети – сумма весов всех дуг сети.

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

Алгоритм Дейкстры.

1)Положим метку , метки всех остальных вершин .?

Множество окрашенных вершин .?

2)Пересчитываются метки всех неокрашенных вершин :

, среди них выбираются вершины с наименьшей меткой и окрашиваются одна из дуг , которая инцидентна.

3)Если все вершины окрашены, то конец алгоритма – длина кратчайшего пути, окрашенные дуги – длина кратчайшего пути; в противном случае переходим к шагу 2.