Developer Cafe

1959년 에드거 데이크스트라가 최단 경로 문제를 푸는 굉장히 흥미로운 알고리즘을 만들었다. 1. 시작 정점을 현재 정점으로 한다. 2. 현재 정점에 인접한 모든 정점을 확인해서 시작 정점으로부터 알려진 모든 위치까지의 가중치를 계산하고 기록한다. 3. 다음 현재 정점을 결정하려면 시작 정점으로부터 도달할 수 있는 방문하지 않은 가장 저렴한 알려진 정점을 찾는다. 4. 그래프 내 모든 정점을 방문할 때까지 1~3단계를 반복한다. 0에 갈 수 있는 정점은 4, 1, 5 이다. 이들의 최단 거리를 저장한다. 이어 가장 가까운 최단거리인 4를 다음 정점으로 한다. 4에서 갈 수 있는 6, 1, 3의 최단 거리를 0에서 시작하는 거리값으로 저장한다. 예를 들어 6인 경우는 3+5이니 8이다. 그러므로 8을 저장..