최단 경로(Shortest Paths)

최단경로

• 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다.
• 다양한 문제 상황
• 각 지점은 그래프에서 노드(Vertex)로 표현
• 지점 간 연결된 도로는 그래프에서 간선(Edge)으로 표현

※조건

1. 유향 그래프

노드(Vertex)와 노드 사이에는 방향성이 있는 간선(Edge)이 주어져야 하며, 무향 그래프인 경우에는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다. 즉, 무향 간선(u, v)는 유향 간선 (u, v)와 (v, u)를 의미한다고 가정한다. 무향인 경우에는 최단 경로를 구할 수 없다.

 

2. 간선 가중치

노드와 노드 사이의 간선에는 무조건 가중치가 부여되어야 한다.

 

※두 정점 사이의 최단 경로

1. 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로

2. 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않는다.

 

※단일 시작점 최단경로

1. 단일 시작점으로부터 각 정점에 이르는 최단경로를 구한다.

다시말해, 그래프의 시작점이 주어진다는 의미이다.

▶ 다익스트라 알고리즘

음의 가중치를 허용하지 않는 최단 경로

가중치(weigt)는 0보다 커야 한다.

▶ 벨만-포드 알고리즘

음의 가중치를 허용하는 최단 경로

가중치(weigt)는 음수일 수 있다. (최단경로는 가중치가 낮을수록 이득이기 때문에 '+'가 손해, '-'는 이득)

▶ 싸이클이 없는 그래프의 최단 경로

 

※모든 쌍 최단경로

1. 모든 정점 쌍 사이의 최단경로를 구한다.(시작점이 주어지지 않는다)

▶ 플로이드-워샬 알고리즘