Algorytm Dijkstry (najkrótsze drogi od 1. węzła do każdego innego)

  1. Nadać każdemu węzłowi cechę (*,∞), tylko pierwszemu węzłowi cechę (*,0). Wszystkie węzły są niesprawdzone.

  2. Wybrać (jeden, wszystko jedno który) węzeł niesprawdzony, którego 2. część cechy jest minimalna

  3. Oznaczyć go jako węzeł sprawdzany (^)

  4. Rozważyć wszystkie łuki rozpoczynające się w węźle sprawdzanym (^), a kończące się w niesprawdzonych (nie *). Jeśli suma (2. cecha węzła sprawdzanego + długość łuku) jest mniejsza od 2. cechy końca łuku, zmienić cechę końca łuku na (węzeł sprawdzany, 2. cecha węzła sprawdzanego + długość łuku), w przeciwnym przypadku nie robić nic.

  5. Węzeł sprawdzany (^) staje się sprawdzonym (*).

  6. Jeśli jest jeszcze choć jeden węzeł niesprawdzony (nie *), idź do 2.

  7. Odczytać najkrótsze drogi od 1. węzła do każdego innego: druga część ostatniej cehcy to długość drogi, samą drogę odczytujemy „od tyłu” z 1. części cech.

Algorytm Floyda (najkrótsze drogi od każdego węzła do każdego)

  1. Macierz A: Macierz odległości między węzłami w połączeniach bezpośrednich (od „rzędu” do „kolumny”); Macierz B: pusta

  2. i=1

  3. Dla każdego elementu macierzy A (rząd - kolumna): jeśli suma (odległość z A „rząd-węzeł i” + odległość z A „węzeł i-kolumna”) jest mniejsza od „odległość z A „rząd-kolumna”, zastąp w A obecny element sumą (odległość z A „rząd-węzeł i” + odległość z A „węzeł i-kolumna”), a w odpowiednim miejscu w B wpisz i, w przeciwnym przypadku nie rób nic

  4. jeśli i jest mniejsze od liczby węzłów, i:=i+1 i idź do 3, w przeciwnym przypadku koniec.

1

2

3

4

5

1

-

2

5

-

-

2

-

-

1

-

7

3

-

-

-

1

-

4

-

-

-

-

4

5

-

-

-

-

-

1

2

3

4

5

6

1

-

2

-

6

2

-

2

-

-

1

-

-

7

3

-

-

-

-

1

-

4

-

-

-

-

-

6

5

-

-

-

-

-

1

6

-

-

-

-

-

-

1

2

3

4

5

6

1

-

8

-

6

-

3

2

8

-

2

5

2

-

3

-

2

-

-

5

8

4

6

5

-

-

2

1

5

-

2

5

*

-

2

6

3

-

8

1

2

-