Рубрики

Алгоритм Флойда Варшалла | DP-16

Графы, Динамическое программирование

Алгоритм Флойда Варшалла предназначен для решения проблемы кратчайшего пути всех пар. Задача состоит в том, чтобы найти кратчайшие расстояния между каждой парой вершин в заданном граничном взвешенном ориентированном графе.

Пример:

Input:
       graph[][] = { {0,   5,  INF, 10},
                    {INF,  0,  3,  INF},
                    {INF, INF, 0,   1},
                    {INF, INF, INF, 0} }
which represents the following graph
             10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3       
Note that the value of graph[i][j] is 0 if i is equal to j 
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.

Output:
Shortest distance matrix
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

Алгоритм Флойда Варшалла
В качестве первого шага мы инициализируем матрицу решения так же, как матрицу входного графа. Затем мы обновляем матрицу решения, рассматривая все вершины как промежуточную вершину. Идея состоит в том, чтобы один за другим выбрать все вершины и обновить все кратчайшие пути, которые включают выбранную вершину в качестве промежуточной вершины кратчайшего пути. Когда мы выбираем число вершин k в качестве промежуточной вершины, мы уже рассматривали вершины {0, 1, 2, .. k-1} как промежуточные вершины. Для каждой пары (i, j) исходных и конечных вершин соответственно существует два возможных случая.
1) k не является промежуточной вершиной кратчайшего пути из i в j. Мы сохраняем значение dist [i] [j] как есть.
2) k — промежуточная вершина кратчайшего пути из i в j. Мы обновляем значение dist [i] [j] как dist [i] [k] + dist [k] [j], если dist [i] [j]> dist [i] [k] + dist [k] [ J]

На следующем рисунке показано указанное выше оптимальное свойство подструктуры в задаче кратчайшего пути для всех пар.

Ниже приведены реализации алгоритма Флойда Варшалла.

C ++

// C ++ программа для алгоритма Флойда Варшалла
#include <bits/stdc++.h>

using namespace std;

  
// Количество вершин в графе
#define V 4 

  
/ * Определить Infinite как достаточно большой
значение. Это значение будет использоваться для
вершины не связаны друг с другом * /
#define INF 99999 

  
// Функция для печати матрицы решения

void printSolution(int dist[][V]); 

  
// Решаем кратчайший путь всех пар
// проблема с использованием алгоритма Флойда Варшалла

void floydWarshall (int graph[][V]) 

{ 

    / * dist [] [] будет выходной матрицей

    что, наконец, будет самым коротким

    расстояния между каждой парой вершин * /

    int dist[V][V], i, j, k; 

  

    / * Инициализировать матрицу решения так же

    в качестве матрицы входного графика. Или мы можем сказать

    начальные значения кратчайших расстояний

    основаны на кратчайших путях с учетом

    промежуточной вершины нет. * /

    for (i = 0; i < V; i++) 

        for (j = 0; j < V; j++) 

            dist[i][j] = graph[i][j]; 

  

    / * Добавить все вершины одну за другой

    множество промежуточных вершин.

    ---> Перед началом итерации,

    у нас самые короткие расстояния между всеми

    пары вершин такие, что

    кратчайшие расстояния учитывают только

    вершины из множества {0, 1, 2, .. k-1} как

    промежуточные вершины.

    ----> После окончания итерации,

    вершина № К добавляется в набор

    промежуточные вершины и множество становится {0, 1, 2, .. k} * /

    for (k = 0; k < V; k++) 

    { 

        // Выбрать все вершины как источник по очереди

        for (i = 0; i < V; i++) 

        { 

            // Выбрать все вершины в качестве места назначения для

            // выше выбранного источника

            for (j = 0; j < V; j++) 

            { 

                // Если вершина k находится на кратчайшем пути из

                // от i до j, затем обновляем значение dist [i] [j]

                if (dist[i][k] + dist[k][j] < dist[i][j]) 

                    dist[i][j] = dist[i][k] + dist[k][j]; 

            } 

        } 

    } 

  

    // Распечатать матрицу кратчайшего расстояния

    printSolution(dist); 

} 

  
/ * Утилита для печати решения * /

void printSolution(int dist[][V]) 

{ 

    cout<<"The following matrix shows the shortest distances"

            " between every pair of vertices \n"; 

    for (int i = 0; i < V; i++) 

    { 

        for (int j = 0; j < V; j++) 

        { 

            if (dist[i][j] == INF) 

                cout<<"INF"<<"     "; 

            else

                cout<<dist[i][j]<<"     "; 

        } 

        cout<<endl; 

    } 

} 

  
// Код драйвера

int main() 

{ 

    / * Давайте создадим следующий взвешенный график

            10

    (0) -------> (3)

        | / | /

    5 | |

        | | 1

    / | / |

    (1) -------> (2)

            3 * /

    int graph[V][V] = { {0, 5, INF, 10}, 

                        {INF, 0, 3, INF}, 

                        {INF, INF, 0, 1}, 

                        {INF, INF, INF, 0} 

                    }; 

  

    // Распечатать решение

    floydWarshall(graph); 

    return 0; 

} 

  
// Этот код предоставлен rathbhupendra

С

// C Программа для алгоритма Флойда Варшалла
#include<stdio.h>

  
// Количество вершин в графе
#define V 4

  
/ * Определить Infinite как достаточно большое значение. Это значение будет использовано

  для вершин, не связанных друг с другом * /

#define INF 99999

  
// Функция для печати матрицы решения

void printSolution(int dist[][V]);

  
// Решает проблему кратчайшего пути для всех пар, используя алгоритм Флойда Варшалла

void floydWarshall (int graph[][V])

{

    / * dist [] [] будет выходной матрицей, которая, наконец, будет самой короткой

      расстояния между каждой парой вершин * /

    int dist[V][V], i, j, k;

  

    / * Инициализировать матрицу решения так же, как матрицу входного графа. Или

       мы можем сказать, что начальные значения кратчайших расстояний основаны

       на кратчайших путях без учета промежуточной вершины. * /

    for (i = 0; i < V; i++)

        for (j = 0; j < V; j++)

            dist[i][j] = graph[i][j];

  

    / * Добавить все вершины одну за другой в набор промежуточных вершин.

      ---> Перед началом итерации у нас есть кратчайшие расстояния между всеми

      пары вершин, так что кратчайшие расстояния учитывают только

      вершины из множества {0, 1, 2, .. k-1} в качестве промежуточных вершин.

      ----> После окончания итерации вершины нет. К добавляется в набор

      промежуточные вершины и множество становится {0, 1, 2, .. k} * /

    for (k = 0; k < V; k++)

    {

        // Выбрать все вершины как источник по очереди

        for (i = 0; i < V; i++)

        {

            // Выбрать все вершины в качестве места назначения для

            // выше выбранного источника

            for (j = 0; j < V; j++)

            {

                // Если вершина k находится на кратчайшем пути из

                // от i до j, затем обновляем значение dist [i] [j]

                if (dist[i][k] + dist[k][j] < dist[i][j])

                    dist[i][j] = dist[i][k] + dist[k][j];

            }

        }

    }

  

    // Распечатать матрицу кратчайшего расстояния

    printSolution(dist);

}

  
/ * Утилита для печати решения * /

void printSolution(int dist[][V])

{

    printf ("The following matrix shows the shortest distances"

            " between every pair of vertices \n");

    for (int i = 0; i < V; i++)

    {

        for (int j = 0; j < V; j++)

        {

            if (dist[i][j] == INF)

                printf("%7s", "INF");

            else

                printf ("%7d", dist[i][j]);

        }

        printf("\n");

    }

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    / * Давайте создадим следующий взвешенный график

            10

       (0) -------> (3)

        | / | /

      5 | |

        | | 1

       / | / |

       (1) -------> (2)

            3 * /

    int graph[V][V] = { {0,   5,  INF, 10},

                        {INF, 0,   3, INF},

                        {INF, INF, 0,   1},

                        {INF, INF, INF, 0}

                      };

  

    // Распечатать решение

    floydWarshall(graph);

    return 0;

}

Джава

// Java-программа для Floyd Warshall All Pairs Shortest
// Алгоритм пути.

import java.util.*;

import java.lang.*;

import java.io.*;

  

  

class AllPairShortestPath

{

    final static int INF = 99999, V = 4;

  

    void floydWarshall(int graph[][])

    {

        int dist[][] = new int[V][V];

        int i, j, k;

  

        / * Инициализировать матрицу решения так же, как матрицу входного графа.

           Или мы можем сказать начальные значения кратчайших расстояний

           основаны на кратчайших путях без учета промежуточных

           вершина. * /

        for (i = 0; i < V; i++)

            for (j = 0; j < V; j++)

                dist[i][j] = graph[i][j];

  

        / * Добавить все вершины по одной к набору промежуточных

           Вершины.

          ---> Перед началом итерации у нас самое короткое

               расстояния между всеми парами вершин, так что

               кратчайшие расстояния учитывают только вершины в

               установите {0, 1, 2, .. k-1} в качестве промежуточных вершин.

          ----> После окончания итерации вершины нет. К добавлено

                на множество промежуточных вершин и множество

                становится {0, 1, 2, .. k} * /

        for (k = 0; k < V; k++)

        {

            // Выбрать все вершины как источник по очереди

            for (i = 0; i < V; i++)

            {

                // Выбрать все вершины в качестве места назначения для

                // выше выбранного источника

                for (j = 0; j < V; j++)

                {

                    // Если вершина k находится на кратчайшем пути из

                    // от i до j, затем обновляем значение dist [i] [j]

                    if (dist[i][k] + dist[k][j] < dist[i][j])

                        dist[i][j] = dist[i][k] + dist[k][j];

                }

            }

        }

  

        // Распечатать матрицу кратчайшего расстояния

        printSolution(dist);

    }

  

    void printSolution(int dist[][])

    {

        System.out.println("The following matrix shows the shortest "+

                         "distances between every pair of vertices");

        for (int i=0; i<V; ++i)

        {

            for (int j=0; j<V; ++j)

            {

                if (dist[i][j]==INF)

                    System.out.print("INF ");

                else

                    System.out.print(dist[i][j]+"   ");

            }

            System.out.println();

        }

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main (String[] args)

    {

        / * Давайте создадим следующий взвешенный график

           10

        (0) -------> (3)

        | / | /

        5 | |

        | | 1

        / | / |

        (1) -------> (2)

           3 * /

        int graph[][] = { {0,   5,  INF, 10},

                          {INF, 0,   3, INF},

                          {INF, INF, 0,   1},

                          {INF, INF, INF, 0}

                        };

        AllPairShortestPath a = new AllPairShortestPath();

  

        // Распечатать решение

        a.floydWarshall(graph);

    }

}

  
// Аакаш Хасия

питон

# Программа Python для алгоритма Флойда Варшалла

  
# Количество вершин в графе

V = 4 

  
# Определить бесконечность как достаточно большое значение. Это значение будет
# используется для вершин, не связанных друг с другом

INF  = 99999

  
# Решает все пары кратчайшего пути с помощью алгоритма Флойда Варшалла

def floydWarshall(graph):

  

    "" "dist [] [] будет выходной матрицей, которая, наконец,

        иметь кратчайшие расстояния между каждой парой вершин "" "

    «» »инициализирует матрицу решения так же, как матрицу входного графа

    ИЛИ мы можем сказать, что начальные значения кратчайших расстояний

    основаны на кратчайших путях с учетом нет

    промежуточные вершины "" "

    dist = map(lambda i : map(lambda j : j , i) , graph)

      

    "" "Добавьте все вершины одну за другой к набору промежуточных

     Вершины.

     ---> До начала итерации у нас самые короткие расстояния

     между всеми парами вершин, так что самый короткий

     расстояния учитывают только вершины из множества

    {0, 1, 2, .. k-1} как промежуточные вершины.

      ----> После окончания итерации вершины нет. к есть

     добавляется к набору промежуточных вершин и

    набор становится {0, 1, 2, .. k}

    «»»

    for k in range(V):

  

        # выбрать все вершины один за другим как источник

        for i in range(V):

  

            # Выберите все вершины в качестве пункта назначения для

            # выше выбранного источника

            for j in range(V):

  

                # Если вершина k находится на кратчайшем пути из

                # от i до j, затем обновите значение dist [i] [j]

                dist[i][j] = min(dist[i][j] ,

                                  dist[i][k]+ dist[k][j]

                                )

    printSolution(dist)

  

  
# Утилита для печати решения

def printSolution(dist):

    print "Following matrix shows the shortest distances\

 between every pair of vertices"

    for i in range(V):

        for j in range(V):

            if(dist[i][j] == INF):

                print "%7s" %("INF"),

            else:

                print "%7d\t" %(dist[i][j]),

            if j == V-1:

                print ""

  

  

  
# Драйвер программы для проверки вышеуказанной программы
# Давайте создадим следующий взвешенный график
«»»

            10

       (0) -------> (3)

        | / | /

      5 | |

        | | 1

       / | / |

       (1) -------> (2)

            3 "" "

graph = [[0,5,INF,10],

             [INF,0,3,INF],

             [INF, INF, 0,   1],

             [INF, INF, INF, 0]

        ]

# Распечатать решение
floydWarshall(graph);
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// AC # программа для Флойд Варшалл Все
// Алгоритм пар кратчайшего пути.

  

using System;

  

public class AllPairShortestPath

{

    readonly static int INF = 99999, V = 4;

  

    void floydWarshall(int[,] graph)

    {

        int[,] dist = new int[V, V];

        int i, j, k;

  

        // Инициализируем матрицу решения

        // так же, как матрица входного графа

        // Или мы можем сказать начальный

        // значения кратчайших расстояний

        // основаны на кратчайших путях

        // учитывая отсутствие промежуточного

        // вершина

        for (i = 0; i < V; i++) {

            for (j = 0; j < V; j++) {

                dist[i, j] = graph[i, j];

            }

        }

  

        / * Добавить все вершины одну за другой

        множество промежуточных вершин.

        ---> Перед началом итерации,

             у нас самые короткие расстояния

             между всеми парами вершин

             такие, что самые короткие расстояния

             рассмотреть только вершины в

             установить {0, 1, 2, .. k-1} как

             промежуточные вершины.

        ---> После окончания итерации

             вершина № К добавлено

             к набору промежуточных

             вершины и множество

             становится {0, 1, 2, .. k} * /

        for (k = 0; k < V; k++)

        {

            // Выбрать все вершины в качестве источника

            // по одному

            for (i = 0; i < V; i++)

            {

                // Выбрать все вершины в качестве пункта назначения

                // для указанного выше источника

                for (j = 0; j < V; j++)

                {

                    // Если вершина k самая короткая

                    // путь от i до j, затем обновляем

                    // значение dist [i] [j]

                    if (dist[i, k] + dist[k, j] < dist[i, j]) 

                    {

                        dist[i, j] = dist[i, k] + dist[k, j];

                    }

                }

            }

        }

  

        // Распечатать матрицу кратчайшего расстояния

        printSolution(dist);

    }

  

    void printSolution(int[,] dist)

    {

        Console.WriteLine("Following matrix shows the shortest "+

                        "distances between every pair of vertices");

        for (int i = 0; i < V; ++i)

        {

            for (int j = 0; j < V; ++j)

            {

                if (dist[i, j] == INF) {

                    Console.Write("INF ");

                } else {

                    Console.Write(dist[i, j] + " ");

                }

            }

              

            Console.WriteLine();

        }

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        / * Давайте создадим следующее

           взвешенный график

              10

        (0) -------> (3)

        | / | /

        5 | |

        | | 1

        / | / |

        (1) -------> (2)

             3 * /

        int[,] graph = { {0, 5, INF, 10},

                        {INF, 0, 3, INF},

                        {INF, INF, 0, 1},

                        {INF, INF, INF, 0}

                        };

          

        AllPairShortestPath a = new AllPairShortestPath();

  

        // Распечатать решение

        a.floydWarshall(graph);

    }

}

  
// Эта статья предоставлена
// Абдул Матин Мохаммед

PHP

<?php
// PHP программа для алгоритма Флойда Варшалла

  
// Решает проблему кратчайшего пути всех пар
// используя алгоритм Флойда Варшалла

function floydWarshall ($graph, $V, $INF) 

{ 

    / * dist [] [] будет выходной матрицей

    что, наконец, будет самым коротким

    расстояния между каждой парой вершин * /

    $dist = array(array(0,0,0,0),

                  array(0,0,0,0),

                  array(0,0,0,0),

                  array(0,0,0,0));

  

    / * Инициализировать матрицу решения так же

    в качестве матрицы входного графика. Или мы можем сказать

    начальные значения кратчайших расстояний

    на основе кратчайших путей с учетом нет

    промежуточная вершина. * /

    for ($i = 0; $i < $V; $i++) 

        for ($j = 0; $j < $V; $j++) 

            $dist[$i][$j] = $graph[$i][$j]; 

  

    / * Добавить все вершины одну за другой в набор

    промежуточных вершин.

    ---> Перед началом итерации имеем

    кратчайшие расстояния между всеми парами

    вершины такие, что кратчайшие расстояния

    рассмотреть только вершины из множества

    {0, 1, 2, .. k-1} как промежуточные вершины.

    ----> После окончания итерации вершина

    нет. к добавляется набор промежуточных

    вершины и множество становится {0, 1, 2, .. k} * /

    for ($k = 0; $k < $V; $k++) 

    { 

        // Выбрать все вершины как источник по очереди

        for ($i = 0; $i < $V; $i++) 

        { 

            // Выбрать все вершины в качестве пункта назначения

            // для указанного выше источника

            for ($j = 0; $j < $V; $j++) 

            { 

                // Если вершина k находится на кратчайшем пути из

                // от i до j, затем обновляем значение dist [i] [j]

                if ($dist[$i][$k] + $dist[$k][$j] < 

                                    $dist[$i][$j]) 

                    $dist[$i][$j] = $dist[$i][$k] +

                                    $dist[$k][$j]; 

            } 

        } 

    } 

  

    // Распечатать матрицу кратчайшего расстояния

    printSolution($dist, $V, $INF); 

} 

  
/ * Утилита для печати решения * /

function printSolution($dist, $V, $INF) 

{ 

    echo "The following matrix shows the " .

             "shortest distances between " . 

                "every pair of vertices \n"; 

    for ($i = 0; $i < $V; $i++) 

    { 

        for ($j = 0; $j < $V; $j++) 

        { 

            if ($dist[$i][$j] == $INF) 

                echo "INF " ; 

            else

                echo $dist[$i][$j], " ";

        } 

        echo "\n"; 

    } 

} 

  
// Код драйвера

  
// Количество вершин в графе

$V = 4 ;

  
/ * Определить Infinite как достаточно большой
значение. Это значение будет использоваться для
вершины не связаны друг с другом * /

$INF = 99999 ;

  
/ * Давайте создадим следующий взвешенный график

        10

(0) -------> (3)

    | / | /

5 | |

    | | 1

/ | / |
(1) -------> (2)

        3 * /

$graph = array(array(0, 5, $INF, 10), 

               array($INF, 0, 3, $INF), 

               array($INF, $INF, 0, 1), 

               array($INF, $INF, $INF, 0)); 

  
// Распечатать решение

floydWarshall($graph, $V, $INF); 

  
// Этот код предоставлен Ryuga
?>

Выход:

Following matrix shows the shortest distances between every pair of vertices
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

Сложность времени: O (V ^ 3)

Вышеуказанная программа печатает только самые короткие расстояния. Мы можем изменить решение для печати кратчайших путей, также сохранив информацию о предшественнике в отдельной 2D-матрице.
Кроме того, значение INF может быть взято как INT_MAX из limit.h, чтобы убедиться, что мы обрабатываем максимально возможное значение. Когда мы принимаем INF в качестве INT_MAX, нам нужно изменить условие if в вышеуказанной программе, чтобы избежать арифметического переполнения.

#include 

#define INF INT_MAX
..........................
if ( dist[i][k] != INF && 
     dist[k][j] != INF && 
     dist[i][k] + dist[k][j] < dist[i][j]
    )
 dist[i][j] = dist[i][k] + dist[k][j];
...........................

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

Рекомендуемые посты:

Алгоритм Флойда Варшалла | DP-16

0.00 (0%) 0 votes