A010_FloydWarshall

 Warshall은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안하였고, Floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안하였다. 그래서 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘을 플로이드-워샬 알고리즘이라 한다. 

 플로이드 알고리즘의 시간복잡도는 O(n3)으로 다익스트라 알고리즘을 n번 사용할 때의 시간복잡도와 동일하지만 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다.

 

플로이드 알고리즘은 모든 점을 경유 가능한 점들로 고려하면서 모든 쌍의 최단 경로의 거리를 계산한다. 이것은 점 1∼n까지의 모든 점을 경유 가능한 점들로 고려하면서, 모든 쌍의 최단 경로의 거리를 계산하는 것이다.

 

다음과 같은 입출력이 가능한 코드를 만들어보았다.

입력 : 2차원 배열 D, 단, D[i,j]=선분 (i,j)의 가중치, 만일 선분 (i,j)가 존재하지 않으면 D[i,j]=∞, 모든 i에 대하여 D[i,i]=0이다.

출력 :  모든 쌍 최단 경로의 거리를 저장한 2차원 배열 D

 

using System;

namespace FloydWarshall
{
  class Program
  {
    static int V = 5;  // Number of vertices
    const int Inf = 100;  // Infinity, not connected

    static void Main(string[] args)
    {
      int[,] graph = {
        { 0, 4, 2, 5, Inf },
        { Inf, 0, 1, Inf, 4 },
        { 1, 3, 0, 1, 2 },
        { -2, Inf, Inf, 0, 2 },
        { Inf, -3, 3, 1, 0 }
      };

      FloydWarshall(graph, V);
    }

    private static void FloydWarshall(int[,] graph, int V)
    {
      Console.WriteLine("graph");
      PrintDist(graph, V);

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

      for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
          if (i != j)
            next[i, j] = j + 1;

      Console.WriteLine("next");
      PrintNext(next, V);

      for (int k = 0; k < V; k++)
      {
        for (int i = 0; i < V; i++)
          for (int j = 0; j < V; j++)
            if (graph[i,k] != Inf && graph[k,j] != Inf && 
              graph[i, k] + graph[k, j] < graph[i, j])
            {
              Console.WriteLine("Change: [{0},{1}] = [{2},{3}] + [{4},{5}] = {6}", 
                i, j, i, k, k, j, graph[i, k] + graph[k, j]);
              graph[i, j] = graph[i, k] + graph[k, j];
              next[i, j] = next[i, k];
            }

        Console.WriteLine("Dist({0})", k);
        PrintDist(graph, V);
        Console.WriteLine("Next({0})", k);
        PrintNext(next, V);
      }

      PrintResult(graph, next);
    }

    private static void PrintNext(int[,] next, int v)
    {
      for (int i = 0; i < v; i++) {
        for (int j = 0; j < v; j++)
          Console.Write("{0,8}", next[i, j]);
        Console.WriteLine();
      }
    }

    private static void PrintDist(int[,] graph, int V)
    {
      for (int i = 0; i < V; i++)
      {
        for (int j = 0; j < V; j++)
          Console.Write("{0,8}", graph[i, j]);
        Console.WriteLine();
      }
    }

    private static void PrintResult(int[,] graph, int[,] next)
    {
      // index는 0~V-1이고 Vertex는 1~V이므로 
      Console.WriteLine("pair     distance    path");
      for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
          if (i != j)
          {
            int u = i + 1;
            int v = j + 1;
            string path = string.Format("{0} -> {1}    {2,2:G}     {3}", u, v, graph[i, j], u);
            do
            {
              u = next[u - 1, v - 1];
              path += " -> " + u;
            } while (u != v);
            Console.WriteLine(path);
          }        
    }
  }
}