Алгоритм Форда-Беллмана

Необходимо найти кратчайшие расстояния в графе от заданной вершины до всех остальных

Алгоритм основан на динамическом программировании, поэтому работает для любых графов. С помощью него так же можно находить циклы отрицательного веса.

Асимптотика

Граф задан матрицей весов O(N³)
Граф задан списком рёбер O(NM)

Листинг C++ - матрица весов

void ford_bellman (int x, vector < vector < int > > &D,
                        vector < int > &w, vector < int > &p)
{
    int i, j, k;
    int n = D.size ();
    w.assign (n, 0);
    p.assign (n, - 1);
    for (i = 0; i < n; ++ i)
        w[i] = D[x][i];
    w[x] = 0;

    for (k = 0; k < n; ++ k)
        for (i = 0; i < n; ++ i)
            for (j = 0; j < n; ++ j)
                if (w[i] > w[j] + D[j][i])
                {
                    w[i] = w[j] + D[j][i];
                    p[i] = j;
                }
}
Листинг C++ - список рёбер

const int inf = 1e9;
void ford_bellman (int x, vector < vector < int > > &R, int n,
                        vector < int > &w, vector < int > &p)
{
    int i, j;
    int m = R.size ();
    w.assign (n, inf);
    p.assign (n, - 1);
    w[x] = 0;

    for (i = 0; i < n; ++ i)
        for (j = 0; j < m; ++ j)
            if (w[R[j][1]] > w[R[j][0]] + R[j][2])
            {
                w[R[j][1]] = w[R[j][0]] + R[j][2];
                p[R[j][1]] = R[j][0];
            }
}

19.05.2007, 14:41

По всем вопросам обращаться: rumterg@gmail.com