자료구조 - Shortest Path 학습

Shortest Path(최단 경로) 특징

1. 음수 사이클이 없다.

2. 방향 그래프(directed graph)

3. 가중치 그래프(weighted graph)

4. 경로의 길이 : edge 가중치의 합

최단 경로 알고리즘의 종류

1. 하나의 출발점과 나머지 모든 목적지

• Dijkstra 알고리즘(음수 가중치가 없다.)
• Bellman-Ford 알고리즘(일반적인 경우)

2. 모든(출발점, 목적지) 쌍

• Floyd-Warshall 알고리즘

Dijkstra 알고리즘

코드 참조 : Dijkstra

Relaxation of an edge

ex) distance[1] > distance[0] + w[0,1] == 20 > 8 + 4 ㅡ> distance[1] = distance[0] + w[0,1] = 12

Graph representation

Adjacency matrix

Dijkstra 알고리즘 순서

Floyd-Warshall 알고리즘

코드 참조 : Floyd-Warshall

1. Dynamic Programming(DP)
2. 모든 (출발점, 목적지) 쌍에 대한 최단 경로