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

Здравствуйте.

Описание, предоставленное здесь очень хорошо освещает тему, но тем не менее я умудрился запутаться sad .

К примеру, объясните, пожалуйста, что происходит здесь

        vector<int> path;
        for (int cur=y; ; cur=p[cur]) // "кар" (сокращено от current?) принимает только два значения?..
       {
            path.push_back (cur);
            if (cur == y && path.size() > 1)  break;
        }

И как с помощью этого алгоритма, скажем, вывести все цепочки кратчайших путей. ( например 3-1-2 и т.п.)

Просто хочу разобраться. Надеюсь на помощь.

С уважением.

2

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

Почему он принимает только 2 значения? Он проходит по всему пути, который мы и хотим вывести.

Насчет всех цепочек - их-то можно вывести после небольшой модификации, но зачем это нужно? Количество путей может быть очень велико (растет экспоненциально от длины).

3 Отредактировано Ищущий (2011-11-13 15:16:43)

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

Хорошо, не все а лишь несколько. Это делается по аналогии с выводом отрицательного цикла?

З.Ы. Я уже понял принцип прохождения пути, спасибо.

4

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

Прошу прощения за второй пост подряд - хотел апнуть тему.

В общем со своими проблемами разобрался, алгоритм модифицировал для своих нужд, но столкнулся с проблемой:
если в графе есть два и больше путей между 2-мя вершинами сохраняется лишь один. Как можно решить эту проблему? Подскажите, если не сложно.

5 Отредактировано KADR (2011-11-20 13:47:36)

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

На самом деле можно восстанавливать кратчайший путь и не храня его явно. Если мы уже нашли расстояния до всех вершин от стартовой, то в текущую вершину B мы могли прийти только из тех вершин A, для которых dist(A)+cost(A,B)=dist(B). Таким образом, можно перебрать всех потенциальных предков данной вершины в кратчайшем пути и пойти сразу в несколько, а не в один.