Поиск всех кратчайших путей и расстояний с помощью Floyd-Warshall

Во-первых, немного предыстории: я работаю над созданием простого класса графа с базовыми алгоритмами графа (Дейкстра, Флойд-Уоршалл, Беллман-Форд и т. Д.), Чтобы использовать его в качестве справочного листа для предстоящего соревнования по программированию.

Пока у меня есть работающая версия Floyd-Warshall, но недостатком является то, что пока она дает мне только кратчайшее значение расстояния между двумя узлами, а не кратчайший путь. Желательно, чтобы построение пути происходило внутри самого алгоритма, вместо того, чтобы вызывать другую функцию для его восстановления.

Вот некоторая информация о структурах данных, которые я использую:

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

Вот пример данных графика, который я использую:

INF 10  INF INF INF INF
INF INF 90  15  INF INF
INF INF INF INF INF 20
INF INF INF INF 20  INF
INF INF  5  INF INF INF
INF INF INF INF INF INF

и вот желаемые значения, которые должны быть в переменной "path" (полученной путем запуска Dijkstra из каждого из узлов):

INF  0   4   1   3   2
INF INF  4   1   3   2
INF INF INF INF INF  2
INF INF  4  INF  3   2
INF INF  4  INF INF  2
INF INF INF INF INF INF

Вот ссылка на код, который я сейчас использую для алгоритма: (через PasteBin).

Любая помощь будет принята с благодарностью!

Изменить: Я попробовал код Википедии чтобы сгенерировать матрицу путей и вот результат:

INF INF  4   1   3   4
INF INF  4  INF  3   4
INF INF INF INF INF INF
INF INF  4  INF INF  4
INF INF INF INF INF  2
INF INF INF INF INF INF

Это вроде как работает, но есть проблемы, когда дело доходит до представления «отдельных» шагов. Например, путь от узла 0 к узлу 1 везде не определен. (Но тем не менее, спасибо Nali4Freedom за предложение)


c++ graph algorithm floyd-warshall
person Mr. Llama    schedule 25.10.2010    source источник
comment
Если я правильно это понимаю, согласно первой строке graph есть только одно ребро от узла №0, и оно ведет к узлу №1. Таким образом, первая строка (или, возможно, первый столбец) path должна быть Inf 1 1 1 1 1. Что мне не хватает?   -  person Beta    schedule 26.10.2010
comment
Ах, я понимаю, как вы могли запутаться, сказав «да». Каждая строка в graph перечисляет ребра, выходящие из этого узла, тогда как каждая строка в path содержит путь к node #[row_num]. Например, первая строка правильной диаграммы path означает, что для того, чтобы добраться до узла 0 (строка = 0) из узла 5 (col = 5), следующим узлом на обратном пути будет узел 2. Чтобы добраться до узла 0 из узла 2 мы используем узел 4, затем узел 3, затем узел 1, а затем, наконец, в нашем пункте назначения с узлом 0.   -  person Mr. Llama    schedule 26.10.2010

Ответы (2)


arrow_upward
2
arrow_downward

Ура!

У меня был хороший взгляд на результаты добавления фрагмента кода Википедии, и я придумал адаптер для преобразования его результатов в мои результаты без необходимости вызова отдельной функции:

// Time to clean up the path graph...
for (int st_node = 0; st_node < this->size; st_node++)
{
    for (int end_node = 0; end_node < this->size; end_node++)
    {
        int mid_node = this->path[st_node][end_node];

        if (mid_node == INF)
        {
            // There is no mid_node, it's probably just a single step.
            if (this->graph[st_node][end_node] != INF)
            {
                this->path[st_node][end_node] = st_node;
            }

        } else {
            // The mid_node may be part of a multi-step, find where it leads.
            while (this->path[mid_node][end_node] != INF)
            {
                if (this->path[mid_node][end_node] == mid_node) { break; }  // Infinite loop
                if (this->path[mid_node][end_node] == INF) { break; }   // Dead end

                mid_node = this->path[mid_node][end_node];
            }

            this->path[st_node][end_node] = mid_node;

        }   // IF mid_node
    }   // FOR end_node
}   // FOR st_node

По сути, это компенсирует переход от узла A к узлу B за один шаг (mid_node == INF) путем добавления ребра, если оно существовало в исходном графе. В качестве альтернативы, если узел, на который он указывает, является лишь ступенькой к узлу назначения (this->path[mid_node][end_node] != INF), тогда он копает, пока не найдет, куда он ведет.

Спасибо за помощь, ребята, думаю, мне просто нужно было кому-то подумать вслух!

person Mr. Llama    schedule 25.10.2010

arrow_upward
1
arrow_downward

В Википедии есть полезная информация и псевдокод. В основном вы просто заполняете | V | x | V | матрица 'next', в которой элемент i, j содержит индекс вершины, к которой нужно перейти, чтобы перейти от узла i к узлу j. Кратчайший путь от i до j может быть затем задан как путь от i до next [i] [j] и от next [i] [j] до j. Вы продолжаете рекурсивно декомпозировать путь, пока не получите полный путь.

person David Brown    schedule 25.10.2010
comment
Поверьте, я попробовал, но моя установка работает (значения по умолчанию - INF) не работает должным образом. : \ - person Mr. Llama; 26.10.2010