Dynamic Programming - All-Pairs Shortest Path

All-Pairs Shortest Path

• 무방향 그래프, 웨이트 있음.
• 가능한 모든 최단 거리 쌍 찾기.
• 다익스트라 n번 돌리기?
  ⇒ O(n*(m+n)logn)

---

Floyd Warshall - O(n³)

• D[k][i]][j] 를 구하자. ⇒ 반복문 세번 O(n³)
• D[k][i]][j]는 1, 2, 3, …, k 노드를 거치는 i → j 의 가장 짧은(최단) 거리.
  1, 2, 3, …, k 노드를 전부 거칠 필요는 없고,
  단지 i, …, j 사이에 거칠 수 있는 노드로 1, 2, 3, …, k 가 존재한다는 의미.
  또한 D[k][i][j] 에서 k+1, k+2, … ,n 노드는 사용하지 않음.
• k = n 일 때가 i → j 최단 거리의 최종 답.

k = 0 일 때는 i → j 의 기본 웨이트와 같다.(다른 노드를 거치지 않고 곧 바로)
D[0][i][j] = W[i][j]

D[k-1][i][j] 가 있다고 가정하자.

D[k][i][j] 를 구하기 위해선 DP 점화식을 응용하여
1. (k 노드를 거치지 않은 i→j의 최단거리)와
2. (k 노드를 거친 i→j의 최단거리)를
비교하여 더 짧은 것을 D[k][i][j] 로 결정하면 된다.

이때 1. (k 노드를 거치지 않은 i→j의 최단거리) 는 D[k-1][i][j] 와 같다.
2. (k 노드를 거친 i→j의 최단거리) 는 k를 거쳐야 하므로 i → j의 중간에서 짤라서 k로 연결해주면 된다.
그리고 k 노드는 경로에서 한번만 나와야하는데 (k가 또 나오면 최단거리가 아니고, 애초에 싸이클이다.)
이미 나왔으므로 거치는 노드는 k-1까지만 가능하다.
즉, D[k-1][i][k] + D[k-1][k][j] 와 같다.

따라서 D[k][i][j] = Min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])

int D[n+1][n+1][n+1];

int F(int W[n+1][n+1], int n)
{
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			D[0][i][j] = W[i][j];

	for(k=1; k<=n; k++)
		for(i=1; i<=n; i++)
			for(j=1; j<=n; j++)
				D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j]);
}

---

메모리 절약 #1

• D[k] 를 구할때는 D[k-1]의 정보만이 필요하다. 즉 배열의 두층 만을 사용.
  따라서 D[2][n+1][n+1]로 정의해도 무방.

int D[2][n+1][n+1];

int F(int W[n+1][n+1], int n)
{
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			D[0][i][j] = W[i][j];

	for(k=1; k<=n; k++)
		for(i=1; i<=n; i++)
			for(j=1; j<=n; j++)
				D[k%2][i][j] = min(D[(k-1)%2][i][j], D[(k-1)%2][i][k] + D[(k-1)%2][k][j]);
}

---

메모리 절약 #2

• 메모리 절약 #1 을 통해 k-1과 k 즉, 배열의 두층만 있으면 된다는 것을 알았다.
• 이때 D[k][i][k] = D[k-1][i][k] 이다. (k는 경로에서 한번만 나와야 하므로)
  따라서 2차원 배열만 사용하더라도
  아직 업데이트되지 않은 층에 대하여 충돌이 발생하는 일은 없다.

int D[n+1][n+1];

int F(int W[n+1][n+1], int n)
{
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			D[i][j] = W[i][j];

	for(k=1; k<=n; k++)
		for(i=1; i<=n; i++)
			for(j=1; j<=n; j++)
				D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
}

---

11404번: 플로이드

1504번: 특정한 최단 경로

C# 풀이

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;

namespace BOJ
{
    internal class Boj
    {
       
        public static void Main()
        {
            var ne = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            
            var dp = new long[ne[0] + 1, ne[0] + 1];

            for (int i = 1; i <= ne[0]; i++)
            {
                for (int j = 1; j <= ne[0]; j++)
                {          
                    if (i == j) dp[i, j] = 0;
                    else dp[i, j] = 100000000000;
                }
            }

            for (int i = 0; i < ne[1]; i++)
            {
                var arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                dp[arr[0], arr[1]] = arr[2];
                dp[arr[1], arr[0]] = arr[2];
            }

            var v1v2 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            

            for (int k=1; k <= ne[0]; k++)
            {
                for(int i=1; i <= ne[0]; i++) 
                { 
                    for(int j=1; j <= ne[0]; j++)
                    {
                        dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j]);
                    }
                }
            } // 일단 플로이드 워셜로 최단경로 구하고

            var sol = Math.Min(dp[1, v1v2[0]] + dp[v1v2[0], v1v2[1]] + dp[v1v2[1], ne[0]],
                                dp[1, v1v2[1]] + dp[v1v2[0], v1v2[1]] + dp[v1v2[0], ne[0]]);
            // 연결을 하되 1 -> u -> v -> n  VS  1 -> v -> u -> n 중에 작은거 고르기

            Console.WriteLine(sol >= 100000000000 ? -1 : sol);
        }
    }
}