최단 경로와 다익스트라 알고리즘(Dijkstra Shortcut Path)

최단 경로란?

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

 

하나의 시작 정점에서 끝 정점까지의 최단 경로

1. 다익스트라 알고리즘(Dijkstra)

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

어떤 경로로 가는게 효율적일까? 

특정 시작점에서 도착점까지의 최소거리를 구하자.

 

시작점 0, 나머지는 INF 무한대로 배치.

갈래길을 가기 위해 cost에

원래값(현재 위치의 cost)에 앞으로 갔을때의 갚을 덮어씌운다. (갱신이 아닌 누적)

 

하나의 노드가 끝나면, 그 다음으로 cost가 가장 작은 node로 간다.

방문하지 않은 노드로 가는데 cost에 더해주고, 기존의 길과 비교해서 더 작은 길을 선택한다.

 

가장 cost가 작은 노드로 시작한다.

방문체크하고, 방문하지 않은 노드로 가서 ....반복

 

 

 

 

 

 

 

 

---

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

음의 가중치를 허용한다.

 

 

모든 정점들에 대한 최단 경로

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