[Algorithm] 최단 경로 알고리즘 Dijkstra, Floyd

최단 경로 문제를 푸는 흔히 쓰이는 2가지 알고리즘이 있다.

Dijkstra와 Floyd다. Dijkstra는 한 정점 s에서 다른 모든 정점 사이의 최단 거리를 구한다.

반면 Floyd 알고리즘은 모든 정점 사이의 최단 거리를 구하는 알고리즘이다. 아주 심플하면서도 강력한 최단 경로 알고리즘이다.

먼저 Dijkstra 의 코드다.

#include <iostream>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 7
#define INF 1000
using namespace std;
int weight[MAX_VERTICES][MAX_VERTICES] =
{
 { 0, 7, INF, INF, 3, 10, INF},
 { 7, 0, 4, 10, 2, 6, INF },
 { INF, 4, 0, 2, INF, INF, INF },
 { INF, 10, 2, 0, 11, 9, 4 },
 { 3, 2, INF, 11, 0, INF, 5 },
 { 10, 6, INF, 9, INF, 0, INF },
 { INF, INF, INF, 4, 5, INF, 0 }
};
int dis[MAX_VERTICES];
int found[MAX_VERTICES];
int choose(int distance[], int n, int found[])
{
 int min = INT_MAX;
 int minpos = -1;
 for (int i = 0; i < n; i++){
  if (distance[i] < min&&!found[i]){
   min = distance[i];
   minpos = i;
  }
 }
 return minpos;
};
void shortest_path(int s, int n)
{
 for (int i = 0; i < n; i++){
  dis[i] = weight[s][i];
  found[i] = FALSE;
 }
 found[s] = TRUE;
 dis[s] = 0;
 for (int i = 0; i < n - 2; i++){
  int u = choose(dis, n, found);
  found[u] = TRUE;
  for (int w = 0; w < n; w++)
  if (!found[w])
  if (dis[u] + weight[u][w] < dis[w])
  {
   dis[w] = dis[u] + weight[u][w];
  }
 }
}

int main()
{
 shortest_path(0, MAX_VERTICES);
 return 0;
}




그리고 아래는 Floyd의 코드다.


#include <iostream>
#include <stdio.h>

using namespace std;

int arr[50][50];
int main()
{
 int N; cin >> N;
 for (int i = 1; i <= N; i++)
 for (int j = 1; j <= N; j++)
  cin >> arr[i][j];
 for (int k = 1; k <= N; k++){
  for (int i = 1; i <= N; i++){
   if (i == k) continue;
   for (int j = 1; j <= N; j++){
    if (j == i || j == k) continue;
    if (arr[i][k] + arr[k][j] < arr[i][j]){
     arr[i][j] = arr[i][k] + arr[k][j];
    }
   }
  }
 }
 return 0;
}