---

최단 경로 알고리즘 정리: 다익스트라 vs 플로이드-와샬

---

1. 최단 경로 알고리즘 개요

최단 경로 알고리즘은 다음과 같이 분류

• 단일 출발점(Single-Source): 하나의 노드에서 모든 노드까지의 최단 경로 계산
  → 다익스트라, 벨만-포드(Bellman-Ford)
• 전체 쌍(All-Pairs): 모든 노드 쌍 사이의 최단 경로 계산
  → 플로이드-와샬, 존슨(Johnson)

---

2. 다익스트라 알고리즘

기본 개념

• 그리디(Greedy) 전략 기반
• 음수가 아닌 가중치만 처리 가능
• 우선순위 큐를 사용해 최적화(O((V+E) log V))

동작 원리

1. 출발 노드의 거리를 0, 나머지는 ∞로 초기화
2. 미방문 노드 중 최소 거리 노드 선택
3. 선택 노드의 인접 노드 거리 갱신
4. 모든 노드 방문 시까지 반복

• 그래프에서 출발점과 도착점 사이의 최단 거리를 구하는 알고리즘
• 보통 단일 정점 간 최단 경로 산출 시 사용, 도로 교통망이나 OSPF 등의 네트워크 라우팅 프로토콜에 널리 이용

// ShortestPath() : edge object 객체 저장을 위한 생성자
// key: vertex
// value: list 형태로 연결된 vertex를 표현하여 edge 연결 관계 표현
function ShortestPath() {
  this.edges = {};
}

// addVertex() : 정점 추가(간선 비용 표시를 위해 key/value object 형태로 저장)
ShortestPath.prototype.addVertex = function (vertex) {
  this.edges[vertex] = {};
};

// addEdge() : 간선 추가
ShortestPath.prototype.addEdge = function (srcVertex, dstVertex, weight) {
  this.edges[srcVertex][dstVertex] = weight;
};

// _extractMin() : 최단 거리 노드 검색
ShortestPath.prototype._extractMin = function (queue, dist) {
  let minDistance = Number.POSITIVE_INFINITY;
  let minVertex = null;

  for (let vertex in queue) {
    if (dist[vertex] <= minDistance) {
      minDistance = dist[vertex];
      minVertex = vertex;
    }
  }

  return minVertex;
};

// dijkstra() : 다익스트라 최단 경로 탐색
ShortestPath.prototype.dijkstra = function (start) {
  let queue = {};
  let dist = {};

  for (let vertex in this.edges) {
    dist[vertex] = Number.POSITIVE_INFINITY;
    queue[vertex] = this.edges[vertex];
  }

  dist[start] = 0;
  while (Object.keys(queue).length != 0) {
    let u = this._extractMin(queue, dist);

    delete queue[u];

    for (let neighbor in this.edges[u]) {
      let alt = dist[u] + this.edges[u][neighbor];
      if (alt < dist[neighbor]) dist[neighbor] = alt;
    }
  }

  for (let vertex in this.edges) {
    if (dist[vertex] === Number.POSITIVE_INFINITY)
      delete dist[vertex];

  return dist;
};

---

3. 플로이드-와샬 알고리즘

기본 개념

• 동적 계획법(DP) 기반
• 음수 가중치 허용(단, 음수 사이클 제외)
• 모든 노드 쌍의 최단 경로를 O(V³) 시간에 계산

동작 원리

1. 인접 행렬로 거리 초기화
2. 각 노드를 중간 경유지로 사용해 거리 갱신
3. 3중 반복문으로 모든 조합 검사

• 동적 계획법을 활용해, 그래프에서 가능한 모든 정점 쌍에 대해 최단 거리를 구하는 알고리즘
• 음의 가중치가 있어도 사용 가능하며, 많은 수의 간선으로 이루어져 있는 밀집 그래프(Dense Graph)에 사용 적합

// floydWarshall() : 플로이드-워셜 최단 경로 탐색
ShortestPath.prototype.floydWarshall = function () {
  let dist = {};

  for (let srcVertex in this.edges) {
    dist[srcVertex] = {};
    for (let dstVertex in this.edges) {
      if (srcVertex === dstVertex) dist[srcVertex][dstVertex] = 0;
      else dist[srcVertex][dstVertex] = Number.POSITIVE_INFINITY;
    }
  }

  for (let srcVertex in this.edges) {
    for (let dstVertex in this.edges[srcVertex])
      dist[srcVertex][dstVertex] = this.edges[srcVertex][dstVertex];
  }

  for (let midVertex in this.edges) 
    for (let srcVertex in this.edges)
      for (let dstVertex in this.edges)
        dist[srcVertex][dstVertex] = Math.min(dist[srcVertex][dstVertex], dist[srcVertex][midVertex] + dist[midVertex][dstVertex]);

  for (let srcVertex in this.edges)
    for (let dstVertex in this.edges)
      if (dist[srcVertex][dstVertex] === Number.POSITIVE_INFINITY)
        delete dist[srcVertex][dstVertex];

  return dist;
};

---

4. 알고리즘 비교

기준	다익스트라	플로이드-와샬
계산 범위	단일 출발점	전체 노드 쌍
시간 복잡도	O((V+E) log V)	O(V³)
공간 복잡도	O(V)	O(V²)
가중치 제약	음수 불가	음수 허용(사이클 제외)
최적화 기법	우선순위 큐	동적 계획법
적합 그래프	희소 그래프	밀집 그래프

---

5. 선택 가이드

• 다익스트라가 적합한 경우:

  • 단일 출발점 문제
  • 그래프가 희소하고 가중치가 양수
  • 실시간 경로 계산이 필요할 때

• 플로이드-와샬이 적합한 경우:

  • 전체 노드 쌍의 경로가 필요
  • 그래프가 밀집되어 있음
  • 음수 가중치 존재 시