algorytm.org

Wyznaczanie najkrótszej drogi w grafie dla znanej odległości

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Wyznaczanie najkrótszej drogi w grafie dla znanej odległości
Ocena użytkowników:***** / 13
SłabyŚwietny 
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:
  1. Zainicjuj stos S, odłóż na stos wierzchołek końcowy, czyli ut, podstaw v=ut
  2. while v<>us do
  3. {
  4. znajdź wierzchołek u taki, że D(v)=D(u)+A[u,v]
  5. odłóż u na stosie S
  6. podstaw v=u
  7. }
Przeanalizujmy teraz prosty przykład:
oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
Przyjmujemy Us=1, symbol "*" oznacza nieskończoność:

Image Image
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:
Stos={5}v=5D[v]=5u=?D[u]+A[u,v]=?
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:
Stos={5,6}v=6D[v]=4u=?D[u]+A[u,v]=?
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:
Stos={5,6,4}v=4D[v]=2u=3D[u]+A[u,v]=4+(-2)=4
Stos={5,6,4,3}v=3D[v]=4u=1D[u]+A[u,v]=0+4=4
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)

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 6
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 17 sierpnia 2012 15:33
Dodaj komentarz