NAJKRÓTSZA ŚCIEŻKA

Zadanie: 
Graf skierowany
1. Zbiór wierzchołek wierzchołek

X = {x

1

, x

2

, ..., x

n

};

2. Zbiór krawędzi i ich wartość

L = {l

1

, l

2

, ..., l

m

}.

 Znaleźć:
Najkrótszą ścieżkę od

A

do

B

.  

Σ l

i

= min.

 Algorytm  
1. Rozbijamy graf na strefę tak aby w każdej strefie nie było

wierzchołek jaki są związany między sobą. W każdej

strefie krawędzi wchodzą z jednej strony i wychodzą z

innej.

2. Przepisujemy dla każdej wierzchołki wartość



.

3. Korygujemy wartości wierzchołek od ostatniej strefie

(końca

B

) po pierwszej (początku

A

).

4. Otrzymana wartość wierzchołki

A

wskakuje na wartość

najkrótszej ścieżki.