Distance

• Weighted Graph: each edge has length
• Unweighted Graph: all edges have same length
• Length of a path = sum of all edges
• distance between two nodes = min length of a path (u,v)

BFS (finding distance for unweighted graph)

BFS를 이용하면 특정 점에서 특정 점까지의 최단거리를 선형 시간에 알 수 있다! 대신 unweight에서만 최단거리이다 (edge 수가 최소인 경로를 구한 것이므로)

Dijkstra’s Algorithm (finding distance in weighted graph)

• A 노드에서 C의 거리를 잴 때 A에서 바로 C로 가는 거리 vs B를 거쳐서 C로 가는 거리를 비교해 짧은 쪽을 A에서 C로 가는 거리로 정한다.
• 그러면 모든 점을 탐색하였을 때 최단 경로를 알 수 있다.

예시를 보면서 익히자

1. A에서 B와 C는 4,2가 걸린다.
2. 가장 작은 C부터 보자. C를 거쳐서 B로 가면 3에 갈 수 있으므로 3으로 바꾼다. C를 거치면 D와 E에 6,7로 갈 수 있다.
3. 그 다음으로 작은 B를 보자. B를 거쳐서 C로 가면 6이 걸리므로 바꾸지 않는다. D로 가면 5에 갈 수 있으므로 5로 바꾼다. E로 가면 6이 걸리므로 6으로 바꾼다.
4. D를 거치는 경우, E를 거치는 경우 전부 완료되었다.