Wpisany przez Michał Knasiecki,
09 sierpnia 2005 20:30
Poniższy algorytm służy do wyznaczania w grafie ciągu wierzchołków us, us+1...ut tworzących drogę między wierzchołkami us i ut o długości d(us,ut). jest on najczęściej używany razem z algorytmem wyznaczania najmniejszej odległości między wierzchołkami (algorytm Forda-Bellmana, algorytm Dijkstry). Po wyznaczeniu najkrótszej odległości d(us,ut) między parą wierzchołków w grafie możemy skonstruować drogę między tymi wierzchołkami taką, że suma wag jej krawędzi jest równa d(us,ut).
Chcemy wyznaczyć drogę między wierzchołkami us i ut o najkrótszej długości.
Załóżmy więc, że dla danego grafu opisanego za pomocą macierzy wag krawędzi A wywołaliśmy algorytm wyznaczania najkrótszej odległości od ustalonego wierzchołka (us) do wszystkich pozostałych i w jego wyniku otrzymaliśmy wektor D- tablicę tych odległości. Z wektora tego odczytujemy najmniejszą odległość między wierzchołkami us i ut: D[ut]=d(us, ut).
Po wykonaiu poniższego algorytmu na stosie otrzymamy ciąg wierzchołków us...ut będących drogą między wierzchołkiem us i ut o długości d(us, ut).
Algorytm przebiega w sposób następujący:
oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
Przyjmujemy Us=1, symbol "*" oznacza nieskończoność:
Jak widać z macierzy wag graf ten ma krawędzie o ujemnych wagach, musimy więc zastosować algorytm Forda-Bellmana. W wyniku jego działania otrzymamy wektor D postaci: D[1]=0, D[2]=2, D[3]=4, D[4]=2, D[5]=5, D[6]=4. W implementacji umieszczonej na stronie wierzchołkiem, względem którego wyznacza się najkrótsze odległości jest wierzchołek o indeksie 1, dlatego też D[1]=0. Musimy teraz wybrać drugi wierzchołek- końcowy, niech będzie to wierzchołek nr. 5. Z wektora D odczytujemy najmniejszą odległość między wierzchołkami 1 i 5 D[5]=d(1,5)=5. chcemy wyznaczyć drogę łączącą wierzchołek 1 i 5 o długości równej 5.
Po wykonaniu pierwszej linii algorytmu otrzymamy anstępujące parametry:
Poszukujemy teraz wierzchołka u. Logika nakazuje sprawdzanie wartości D[u]+A[u,v] tylko dla tych wierzchołków u, które są poprzednikami wierzchołka v. W naszym przypadku poprzednikami wierzchołka 5 są wierzchołki 2, 3 i 6. Sprawdzamy więc: D[2]+A[2,5]=2+4=6<>D[5], D[3]+A[3,5]=4+3=7<>D[5] a D[6]+A[6,5]=4+1=5=D[5]. Znależliśmy wierzchołek u=6 wykonujemy zatem instrukcje 5 i 6 algorytmu:
Tym razem nie mamy zbyt dużego wyboru, gdyż jedynym poprzednikiem wierzchołka nr. 6 jest 4. A więc D[4]+A[4,6]=2+2=4=D[6], zatem m=4. Dalej algorytm przebiega podobnie:
Tu algorytm się kończy, gdyż w następnej iteracji v=1. A zatem droga między wierzchołkiem 1 i 5 o długości 5 jest następująca: (1,3,4,6,5)
Chcemy wyznaczyć drogę między wierzchołkami us i ut o najkrótszej długości.
Załóżmy więc, że dla danego grafu opisanego za pomocą macierzy wag krawędzi A wywołaliśmy algorytm wyznaczania najkrótszej odległości od ustalonego wierzchołka (us) do wszystkich pozostałych i w jego wyniku otrzymaliśmy wektor D- tablicę tych odległości. Z wektora tego odczytujemy najmniejszą odległość między wierzchołkami us i ut: D[ut]=d(us, ut).
Po wykonaiu poniższego algorytmu na stosie otrzymamy ciąg wierzchołków us...ut będących drogą między wierzchołkiem us i ut o długości d(us, ut).
Algorytm przebiega w sposób następujący:
- Zainicjuj stos S, odłóż na stos wierzchołek końcowy, czyli ut, podstaw v=ut
- while v<>us do
- {
- znajdź wierzchołek u taki, że D(v)=D(u)+A[u,v]
- odłóż u na stosie S
- podstaw v=u
- }
oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
Przyjmujemy Us=1, symbol "*" oznacza nieskończoność:
![]() |
![]() |
Po wykonaniu pierwszej linii algorytmu otrzymamy anstępujące parametry:
Stos={5} | v=5 | D[v]=5 | u=? | D[u]+A[u,v]=? |
Stos={5,6} | v=6 | D[v]=4 | u=? | D[u]+A[u,v]=? |
Stos={5,6,4} | v=4 | D[v]=2 | u=3 | D[u]+A[u,v]=4+(-2)=4 |
Stos={5,6,4,3} | v=3 | D[v]=4 | u=1 | D[u]+A[u,v]=0+4=4 |
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Michał Knasiecki | C/C++ | .cpp | .cpp | ***** / 7 |
Poprawiony: 17 sierpnia 2012 15:33