자료구조와 알고리즘/Graph

Floyd Warshall (All Pairs Shortest Path)

그레이트쪼 2016. 9. 3. 21:53

Problem definition

  • 그래프에서 모든 노드로부터 모든 노드로의 최단 경로를 구하는 문제
  • Dijkstra를 n번 돌리는 거랑 같지만 이게 더 구현이 간단하다.
  • 문제가 모든 노드로부터 모든 노드까지의 최단 경로 값이기 때문에 결과는 n x n 형태의 테이블이거나 이것들 중에 한 값, 즉 특정 노드에서부터 모든 노드까지 가는 최단 경로의 값이 된다. 
  • 풀이법은 DP이다. 

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      

Output:

Shortest distance matrix

      0      5      8      9

    INF      0      3      4

    INF    INF      0      1

    INF    INF    INF      0


  • 두 정점을 잇는 최소 비용 경로는 아래의 두 경우 중 최소이다.
    • 경유지를 거치거나
    • 거치지 않는 경우
  • 만일 경유지를 거친다면 그것을 이루는 부분 경로 역시 최단 경로이다.


Dijk = min(Dikk-1 + Dkjk-1, Dijk-1)
  • Dijk = 점 {1, 2, …, k}만을 경유 가능한 점들로 고려하여, 점 i로부터 점 j까지의 모든 경로 중에서 가장 짧은 경로의 거리를 의미한다. 즉, 1 ~ k까지의 어떤 점을 지나도 상관없으며 심지어 i에서 j로 직접 가는 경로도 무방하다.
  • k≠i, k≠j, k=0인 경우에는 어떤 점도 경유하지 않는다는 의미에서 Dij0 는 선분 (i, j)의 거리를 의미한다.
  • Dij1 는 점 1을 경유하여 j로 가는 경로와 i에서 j로 직접 가는 경로, 즉 선분 (i, j) 중에서 짧은 거리이다.
  • Dij2 는 점 2을 경유하여 j로 가는 경로와 점 1까지만 후보로 포함시킨 최소 경로로 j로 가는 경로 중에서 짧은 거리이다. 즉 min(Di21 + D2j1, Dij1)가 되겠다.
  • 이를 일반화 하면 Dijk = min(Dikk-1 + Dkjk-1, Dijk-1) 이다.


Code - Dynamic Programming solution (Bottom-up manner)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// Number of vertices in the graph
#define V 4
  
/* Define Infinite as a large enough value. This value will be used
  for vertices not connected to each other */
#define INF 99999
  
// A function to print the solution matrix
void printSolution(int dist[][V]);
  
// Solves the all-pairs shortest path problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V])
{
    /* dist[][] will be the output matrix that will finally have the shortest 
      distances between every pair of vertices */
    int dist[V][V], i, j, k;
  
    /* Initialize the solution matrix same as input graph matrix. Or 
       we can say the initial values of shortest distances are based
       on shortest paths considering no intermediate vertex. */
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
  
    /* Add all vertices one by one to the set of intermediate vertices.
      ---> Before start of a iteration, we have shortest distances between all
      pairs of vertices such that the shortest distances consider only the
      Vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
      ----> After the end of a iteration, vertex no. k is added to the set of
      intermediate vertices and the set becomes {0, 1, 2, .. k} */
    for (k = 0; k < V; k++)
    {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++)
        {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++)
            {
                // If vertex k is on the shortest path from
                // i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
  
    // Print the shortest distance matrix
    printSolution(dist);
}
  
/* A utility function to print solution */
void printSolution(int dist[][V])
{
    printf ("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");
    }
}
  
// driver program to test above function
int main(int argc, char** argv)
{
    int graph[V][V] = {{0,    5, INF,  10},
                        {INF,   0,   3, INF},
                        {INF, INF,   0,   1},
                        {INF, INF, INF,   0}
                        };
  
    // Print the solution
    floydWarshall(graph);
    return 0;
}


Bottom-up 방식을 table로 이해하기



저작자표시