그래프에서 간선에 적혀있는 가중치가 전부 동일하지 않다면, 최단거리를 구하는 일은 생각보다 복잡합니다. 지금부터는 이러한 경우의 최단경로를 구하는 알고리즘에 대해서 소개하겠습니다.1. 다익스트라 (Dijkstra)특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘입니다. 예를 들어 5개의 정점(1 ~ 5번)이 있고 1번 정점에서 출발한다고 가정하면, 1번에서 2 ~ 5번으로 가는 최단거리를 구해줍니다.양의 가중치만 있는 그래프에서만 다익스트라를 이용해 최단거리를 구할 수 있으며, 음의 가중치가 있으면 다시 골라졌던 정점에 도달하는 dist값이 더 작아질 수 있기 때문에 최단거리임을 보장할 수 없게 됩니다. 다익스트라의 아이디어다른 지점까지의 거리는 모르지만, A라는 지점까지 가는 ..
