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

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

5 голосов
/ 26 октября 2010

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

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

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

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 за предложение)

Ответы [ 2 ]

2 голосов
/ 26 октября 2010

ура!

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

// 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), то он копает, пока не найдет, куда ведет.

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

1 голос
/ 26 октября 2010

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

...