최단경로

1. 최단 경로 - 최단 경로 문제는 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. - 최단 경로를 찾는 대표적인 알고리즘으로 다익스트라, 플로이드 워셜, 벨만포드가 있다. 2. 최단 경로 알고리즘 1) 다익스트라(Dijkstra) ① 개념 : 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. ※ 조건 : 음수 가중치와 음수 사이클은 없다고 가정한다. ② 동작 과정 - 시작점으로부터 가장 가까운 정점을 방문 - 방문한 정점에서 인접한 정점들에 대해 거리를 갱신 위와 같은 그래프가 있을 때, v0을 시작노드라고 하면 아래와 같이 거리가 갱신된다. v0 v1 v2 v3 v4 v5 0 50 10 INF 45 INF 그다음 노드를 v2..