[알고리즘] 최단 경로(Shortest Path)

정의

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치 합이 최소인 경로이다.
• 가중치가 없다는 말은 모든 간선의 가중치가 동일하다는 것을 의미. 즉, 하나의 vertex에서 다른 vertex까지 거친 간선의 개수(정점의 개수도 가능)가 최대한 적은 경우가 된다.
• 그리디 유형의 알고리즘

종류

1. 하나의 vertex에서 다른 vertex까지의 최단 경로

• 다익스트라(dijkstra) 알고리즘 > click!

  • 음의 가중치를 허용하지 않는다.

• 벨만-포드(Bellman-Ford) 알고리즘

  • 음의 가중치를 허용한다.

2. 모든 vertex에 대한 최단 경로

• 플로이드-워샬(Floyd-Warchall) 알고리즘