waca's field

# 최단 경로 최단 경로(shortest path)문제는 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제다. 간선의 가중치는 경우에 따라 비용, 거리, 시간 등으로 해석될 수 있다. 아래의 그래프를 살펴보자. 정점 0에서 정점 3으로 가는 최단 경로는 ( 0, 4, 1, 2, 3 )이고 이 때의 비용(거리)은 3 + 2 + 4 + 2 = 11 이다. 정점 0에서 정점 3으로 가는 다른 경로가 얼마든지 존재하지만, 최소의 거리로 갈 수 있는 방법은 이 방법 뿐이다. 가중치는 가중치 인접 행렬이라고 불리는 2차원 배열에 저장된다. 가중치 인접 행렬은 기존의 인접행렬과 차이점이 있다. 기존의 인접 행렬에서는 간선이 없는 구간에는 행렬의 값을 0으로 했었다. 그러나 가..