최단경로 알고리즘

최단 경로 알고리즘의 변형들

• 비가중치 그래프(Unweighted Graph) (BFS)
  • 비가중치 그래프에서 BFS알고리즘을 이용하면 시작점으로 부터 해당 노드까지의 최단경로를 구할 수 있다.
  • BFS는 부모노드와 연결된 자식노드를 모두 탐색하고 다음 레벨로 진행하는 알고리즘이기 때문에 비가중치 그래프에서 연결된 곳들을 거쳐서 현재 노드로 오는 '간선 수'를 세는것 만으로도 최소경로를 구할 수 있다. 이유는 직접연결된 노드가 아니라 다른경로를 거쳐서 현재노드까지 올 수 있다면 이미 최소 간선을 통한 이동 경로가 아니기 때문이다. 비가중치에서는 연결된 노드간 이동거리를 모두 1로 볼 수 있기 때문에 출발점으로 부터 현재 노드까지 '최소간선 수'를 세는 것만으로도 최단경로이다.
• 가중치 그래프(Weighted Graph)의 최단 경로 (BFS,Dijkstra)
• 음수간선(Negative Edge)가 있는 가중치 그래프의 최단경로
• 여기서 비가중치 그래프의 최단경로 문제는 가중치 그래프의 최단경로문제의 특수한 경우라고 생각하면 된다. 비가중치 그래프를 모든 가중치가 1인 경우로 생각하여 가중치 그래프의 최단경로문제를 적용시키면 되기 때문이다. 비가중치 자체도 하나의 특수한 경우로 생각하여 알고리즘을 구현할 수도 있다.