다익스트라 알고리즘 / 플로이드 와샬 알고리즘

다익스트라 알고리즘

: 출발지 정점을 하나 정해놓고 그곳에서부터 다른 모든 정점으로의 최단 경로를 구함.
가장 적은 비용을 하나씩 선택해감 (우선순위 큐)

플로이드 와샬 알고리즘

: 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구함. 즉, 정점과 정점, 모든 쌍의 최단 경로를 구함.

모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고 다이나믹 프로그래밍 방식으로 각 쌍의 최단 거리를 업데이트. (업데이트 기준: 현재 거치는 정점)

거쳐가는 정점을 기준으로 알고리즘 수행. (i->j로 가는 경우 해당 정점을 경유해 가는 것이 빠르다면 그 정점을 거쳐가는 경로로 업데이트)

점화식: distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j]);

i에서 정점 n을 거쳐 j로 갈 때 n을 거쳐 가는 것이 더 최단 경로이면 업데이트.

코드

출처

int INF = 1000000;

int a[4][4] = {
  { 0, 5, INF, 8 },
  { 7, 0, 9, INF },
  { 2, INF, 0, 4 },
  { INF, INF, 3, 0 }
};

// 시간복잡도 V^3
for(int k = 0; k < 4; k++)  {		// k 는 거쳐가는 정점
  for(int i = 0; i < 4; i++)  {		// i 는 행 (출발 정점)
    for(int j = 0; j < 4; j++)  {	// j 는 열 (도착 정점)
      if (a[i][k] + a[k][j] < a[i][j])  {	
      // 점화식
      // distance[i,j] = min(distance[i,j],distance[i,n]+distance[n,j])
        a[i][j] = a[i][k] a[k][j];
     }
   }
  }
}