Algorytm Bellmana-Forda

Z RNO-Wiki
(Różnice między wersjami)
(Problem najkrótszych ścieżek z jednym źródłem)
(Problem najkrótszych ścieżek z jednym źródłem)
Linia 9: Linia 9:
 
Na przykład, dla grafu z powyższego rysunku i źródła w wierzchołku 1, najkrótsze ścieżki można przedstawić w następujący sposób:
 
Na przykład, dla grafu z powyższego rysunku i źródła w wierzchołku 1, najkrótsze ścieżki można przedstawić w następujący sposób:
 
[[File:ShorthestPaths.png|center]]
 
[[File:ShorthestPaths.png|center]]
Aby znaleźć najkrótszą ścieżkę do wierzchołka 2, wystarczy przeglądać pomarańczowe krawędzie chodząc '''wstecz'', zaczynając od wierzchołka 2. Przeglądanie zatrzymujemy, gdy napotkamy wierzchołek źródłowy. Na poniższym rysunku zaznaczono odwiedzone krawędzie, które tworzą najkrótszą ścieżkę do wierzchołka 2.
+
Aby znaleźć najkrótszą ścieżkę do wierzchołka 2, wystarczy rozpocząć przeglądanie grafu od wierzchołka 2, chodząc ''wstecz'' po krawędziach pomarańczowych, aż do napotkania wierzchołka źródłowego.
[[File:ShortestPath.png]]
+
Na poniższym rysunku zaznaczono odwiedzone krawędzie, które tworzą najkrótszą ścieżkę do wierzchołka 2.
Można teraz zauważyć pewną rzecz, która wcale nie wyszła tutaj przypadkowo. Najkrótsze ścieżki do wierzchołków leżących na czerwonej ścieżce zawierają się niej, tzn. jeśli
+
[[File:ShortestPath.png|center]]
 +
Można teraz zauważyć pewną rzecz, która wcale nie wyszła tutaj przypadkowo.
 +
Najkrótsze ścieżki do wierzchołków leżących na czerwonej ścieżce zawierają się w niej, tzn. jeśli
 
  s -> u_1 -> u_2 -> ... -> u_k
 
  s -> u_1 -> u_2 -> ... -> u_k
 
jest najkrótszą ścieżką do wierzchołka ''u_k'', to
 
jest najkrótszą ścieżką do wierzchołka ''u_k'', to

Wersja z 20:16, 9 wrz 2013

Problem najkrótszych ścieżek z jednym źródłem

Rozważmy tym razem graf skierowany $$G=<V,E>$$ z funkcją wagową $$f:E\to R$.

Rysunek
DAG.png
przedstawia przykład takiego grafu. Wagi krawędzi oznaczono kolorem niebieskiem.

Często grafy tego typu mogą reprezentować pewną sieć połączeń, np. między miastami, gdzie wagi oznaczają np. dystans albo raczej koszt przejazdu pomiędzy miastami, bo dystans zwykle nie jest ujemny.

W artykule tym zajmiemy się problemem znajdowania najkrótszych ścieżek z jednego źródła w grafie $$G$$, tj. problemem, w którym dla danego wyróżnionego wierzchołka $$s$$ - źródła (ang. source), chcemy wyznaczyć najkrótsze ścieżki do wszystkich pozostałych wierzchołków w grafie $$G$$; koszt ścieżki definiujemy jako sumę wag wszystkich jej krawędzi.

Na przykład, dla grafu z powyższego rysunku i źródła w wierzchołku 1, najkrótsze ścieżki można przedstawić w następujący sposób:

ShorthestPaths.png

Aby znaleźć najkrótszą ścieżkę do wierzchołka 2, wystarczy rozpocząć przeglądanie grafu od wierzchołka 2, chodząc wstecz po krawędziach pomarańczowych, aż do napotkania wierzchołka źródłowego. Na poniższym rysunku zaznaczono odwiedzone krawędzie, które tworzą najkrótszą ścieżkę do wierzchołka 2.

ShortestPath.png

Można teraz zauważyć pewną rzecz, która wcale nie wyszła tutaj przypadkowo. Najkrótsze ścieżki do wierzchołków leżących na czerwonej ścieżce zawierają się w niej, tzn. jeśli

s -> u_1 -> u_2 -> ... -> u_k

jest najkrótszą ścieżką do wierzchołka u_k, to

s -> u_1 -> u_2 -> ... -> u_j  (j<k)

jest najkrótszą ścieżką do u_j.

Algorytm Bellmana-Forda "problem znajdowania najkrótszej ścieżki"


Algorytm działający dla grafu skierowanego ważonego. Mam nadzieję, że komentarze w kodzie wystarczą do zrozumienia algorytmu ;-)

Złożoność o(n^3)

#include<cstdio>
#include<vector>
 
using namespace std;
 
int n, m, s; //n - liczba wierzchołków, m - liczba krawędzi, s - punkt, z którego zaczynamy
 
vector<vector<int> >E;
vector<int>D;
 
const int INF = (1 << 30); //Jest to wartość na tyle duża, że dla liczb z zakresu int powinna posłużyć jako nieskończoność
 
int main()
{
    scanf("%d %d %d", &n, &m, &s); // wczytujemy podstawowe informacje ze standardowego wejścia
 
    E.resize(m);
 
    for (int i = 0; i < m; i++) //wczytywanie opisu grafu
    {
        int a , b, c;
 
        scanf("%d %d %d", &a, &b, &c);
        E[i].resize(3);
        E[i][0] = a;
        E[i][1] = b;
        E[i][2] = c;
    }
 
    D.resize(n);
 
    for (int i = 0; i < n; i++) D[i]=INF; //D jest tablicą, w której trzymamy "koszt" dotarcia do danego wierzchołka z wierzchołka s. Na początku zakładamy, że dotarcie do reszty wierzchołków jest bardzo drogie
    D[s] = 0; //ale do wierzchołka s możemy dostać się za darmo
    for (int i = 1; i<=n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int a = E[j][0], b = E[j][1], c = E[j][2];
            if (D[a]!=INF && D[a] < D[b]-c) //jeżeli koszt dotarcia do poprzedniego wierzchołka (+7) jest mniejszy niż koszt dostanie się do aktualnego wierzchołka
            {
                D[b] = D[a]+c; //to zamieniamy wartości. Należy pamiętać, aby do wartości z wierzchołka poprzedzającego dodać koszt przejścia po krawędzi do aktualnego wierzchołka
 
                if (i==n) // jeżeli i dojdzie do n i wejdzie do tej pętli znaczy, że odkryliśmy cykl o ujemnej wadze
                {
                    printf("NIE"); //więc program powinien na so tym poinformować i skończyć swoje działanie
                    return 0;
                }
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        if (i!=s && D[i]<INF) printf("%d %d\n", i, D[i]); //wypisywanie wyniku na ekran
    }
    return 0;
}
Osobiste