5.3 최단 거리 알고리즘

1. 다익스트라 알고리즘 

: 간선의 가중치가 음수가 아닌 경우 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘

-> 시작 정점을 설정하고, 방문 가능하면서 비용이 가장 적게 드는 정점에 방문해 비용을 갱신, 우선순위 큐를 사용하면 시간 복잡도 면에서 효율적일 수 있음

 

 

2. 벨만-포드 알고리즘

: 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로, 간선의 가중치가 음수인 경우에도 적용할 수 있음 but 음의 사이클이 있으면 최소 비용이 무한하게 줄어들어서 알고리즘을 적용할 수 없음

-> (정점 개수) -1 만큼 모든 간선을 탐색해야 함