최단 경로 알고리즘

최단 경로

• 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 가중치 합이 최소인 경로
• 다익스트라(Dijkstra) 알고리즘: 음의 가중치가 존재하면 안됨
• 벨만-포드(Bellman-Ford) 알고리즘: 음의 가중치가 있어도 가능
• 플로이드-워셜(Floyd-Warshall): 모든 정점들에 대한 최단 경로를 구할 때 사용

다익스트라 알고리즘

• 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• Greedy 기법을 사용한 알고리즘으로, Prim 알고리즘과 유사
• 다른 노드를 거쳐가는 더 빠른 길이 존재할 수 있기 때문에 무조건 가중치가 작은 간선을 택하면 안된다.
• 가중치가 작은 간선을 선택할 때 PriorityQueue를 사용하면 손쉽게 구할 수 있다.

Prim vs Dijkstra

• Prim: 모든 정점을 연결하는 최소 간선 비용(신장 트리에 연결된 정점에서 자신으로의 최소 간선 비용) 트리. 신장트리에 포함되지 않은 정점 중 최소 간선 비용 선택
• Dijkstra: 출발지에서 자신으로의 최단 거리(최소 비용) 경로. 최소비용이 확정되지 않은 정점 중 출발지로부터 최소 비용 정점 선택(경유지를 고려한 경우도 비교)