최단경로 알고리즘

최단경로 알고리즘은 그래프에서 시간과 비용을 절약하기 위해 존재한다.
따라서 종류와 동작 방식에 대해 알아 볼 예정이다.

Dijkstra 알고리즘

• 하나의 정점으로부터 모든 정점까지의 최단 경로를 계산한다.
  • 집합 S : 시작 정점 v로부터의 최단 경로가 이미 발견된 정점들의 집합
  • 배열 distance : 최단 경로가 알려진 정점들 만을 이용한 다른 정점들까지의 최단 경로 길이

핵심은 최단 경로가 발견된 정점들을 이용하여 다른 정점들의 최단 경로를 알아낸다는 것이다.
C언어로 구현된 코드를 보고 싶다면 링크를 클릭하자.

동작 그림

Floyd 알고리즘

• 모든 정점으로부터 모든 정점까지의 최단 경로를 계산한다.
  • 2차원 배열을 이용하여 3중 반복을 하는 루프로 구성
  • 인접 행렬 weight 구성
    • i == j 이면, weight[i][j] = 0;
    • 두개의 정점 i, j 사이에 간선이 존재하지 않으면, weight[i][j] = 무한대
    • 정점 i, j 사이에 간선이 존재하면, weight[i][j] = 간선의 가중치

[의사 코드]

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

C언어로 구현된 코드를 보고 싶으면 링크를 클릭하자.

동작 그림