Algorytm Bellmana-Forda

Z RNO-Wiki
(Różnice między wersjami)
m (Wycofano edycję użytkownika Pranavwright (dyskusja). Autor przywróconej wersji to Hello.)
Linia 66: Linia 66:
 
}
 
}
 
</source>
 
</source>
 
 
[http://customessays.ws/ Custom essays]
 

Wersja z 21:03, 21 cze 2011

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