Shortest path finding

최단 경로 알고리즘

그래프 내의 서로 다른 두 정점 사이를 연결하는 가중치의 총합이 최소가 되도록 연결하는 방법 찾기

Dijkstra's Algorithm

양수 가중치 간선만으로 이루어진 그래프에서의 최단 경로 탐색

• 구현
  • 현재 단계 정점에서 미방문 정점으로 진출하는 모든 인접 간선을 완화한다.
  • 간선 완화가 완료되면 현재 단계 정점을 미방문 정점 집합에서 제거하고 인접 정점을 방문한다.
  • 목표 정점에 방문하거나 미방문 정점들의 시험적 거리의 최소값이 무한대, 또는 미방문 정점의 집합이 공집합이 되면 알고리즘을 종료한다.

Bellman-Ford Algorithm

음수 가중치 간선을 포함하는 그래프에서의 최단 경로 탐색, 음수 가중치 사이클 확인 과정 존재

• 구현
  • 매 단계별로 그래프 내의 모든 간선을 완화함으로써 경로를 탐색한다.
  • 음수 사이클의 포함 여부를 확인하기 위해 경로를 구한 뒤, 모든 간선에 대한 완화를 1회 수행한다.
    이 때 목표 정점에 도달하기 위한 가중치의 총합이 갱샌되는 경우는 음수 사이클 포함

A* Algorithm

시작 정점으로부터 현재 정점까지의 거리에 휴리스틱 추정값을 더하여 이동 비용을 계산하는 방법

• 구현
  • 현재 단계 정점에서 미방문 인접 정점으로의 이동 비용을 완화한다.
  • 이동 비용 완화가 완료되면 현재 단계 정점을 미방문 정점 집합에서 제거하고, 인접 정점을 방문한다.
  • 목표 정점에 방문하거나 미방문 정점들의 이동 비용의 최소값이 무한대 또는 미방문 정점의 집합이 공집합이 되면 알고리즘을 종료한다.

Floyd-Warshall Algorithm

모든 정점 쌍 간의 최단 경로의 길이 탐색

• 구현
  • 시작 정점을 s, 목표 정점을 e, 경유 정점을 w 라고 하고
    두점 사이의 최단 경로를 저장하는 행렬2차원 배열 D 를 만든다
  • 중간 정점 w에 대하여 D[s][e] > D[s][w] + D[w][e] 인 경우 값을 갱신하는 이중 반복문
    즉, 최종적으로 삼중 반복문 형태의 반복 계산을 수행한다.