Задача о кратчайших путях для всех пар
Здравствуйте, если вы помните алгоритм Дейкстры, который находит кратчайший путь между исходным узлом и всеми остальными узлами, но что, если мы хотим найти кратчайший путь между любыми двумя случайными узлами, присутствующими в графе??
Итак, у нас есть алгоритм под названием Алго Флойда Уоршалла. Он был назван так потому, что алгоритм Уоршелла находит транзитивное замыкание орграфов, а алгоритм Флойда находит кратчайший путь для всех пар. На самом деле, в начале, когда этот алгоритм представили warshall и floyd, они нигде не упоминали DP, но позже обнаружили прикосновение DP в своем алгоритме и затем упомянули его.
Итак, мы представляем граф в виде матрицы смежности и соотв. для алгоритма мы рассматриваем косвенный вес ребра как бесконечность или MAX_INT и D[i][j] = 0, где i==j .
Итак, ниже вы можете увидеть пошаговую методологию этого алгоритма.
Здесь используется следующая формула:
if (R[i][k]+R[k][j] ‹ R[i][j])
{R[i][j] = R[ я][к]+Р[к][дж]}
Используемый алгоритм приведен ниже: -
Код написан мной на языке C++.
Ссылка: https://github.com/halfbloodprince16/All-Algorithms/blob/master/FloydWarshallDP.cpp
Ссылки: Анани Левитин DAA, geeksforgeeks.
