최단경로알고리즘

최단 경로 알고리즘

 

- 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불린다.

 

- 대표적으로는

1. '한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는' 다익스트라 알고리즘

2. '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는' 플로이드 워셜 알고리즘

이 있다.

 

- 보통 '그래프' 를 이용해 표현된다.

1. 각 지점은 '노드'로 , 연결된 도로는 '간선'으로 표현된다

 

다익스트라 알고리즘

- 특정 노드에서 다른 특정 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

- 음의 간선(0보다 작은 값을 가지는 간선) 이 없을 때 사용

- 현실 세계의 gps 알고리즘으로 채택된다 -> 현실세계에서는 음의 간선이 없으므로 가능

- 매 단계 가장 비용이 적은 노드를 선택해서 과정을 반복하므로 그리디 알고리즘으로 분류

 

알고리즘 동작 순서

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택

4. 해당 노들르 거쳐 다른 노드로 가는 비용을 계산 후 최단 거리 테이블 갱신

5. 3/4 번을 반복 수행

 

요약하자면, 다익스트라 알고리즘은 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다.

매번, 현재 처리하고 있는 노드를 기준으로 간선을 확인하며, 짧은 경로 발견시 최단 거리 테이블을 갱신해 나간다.

 

구현

- 힙 자료구조를 사용

* 힙

우선순위 큐를 구현하기 위해 사용하는 자료구조

 

import heapq
import sys
input = sys.stdin.readline
INF = int(10e9)

# 노드의 개수, 간선의 개수를 입력받기
n,m = map(int,input().split())
# 시작 노드의 번호를 입력받기
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
#최단 거리 테이블으 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a,b,c = map(int,input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c 라는 의미
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q: # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heaqpop(a)
        # 현재 노드기 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue

        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

 

플로이드 워셜 알고리즘

- 단계마다 거쳐가는 노드를 기준으로 알고리즘 수행

- 모든 노드(N) 에 대하여 모든 경로(N^2)를 수행하므로 시간복잡도는 O(N^3)이다

- 모든노드 -> 모든노드의 탐색을 수행하므로 최단거리테이블은 2차원 리스트이다

 

구현

INF = int(1e9)

n = int(input())
m = int(input())

# 2차원 리스트를 만드로 모든 값을 무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1,n+1):
    for b in range(1,n+1):
        if a == b:
            graph[a][b] == 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            grpah[a][b] = min(grpah[a][b], graph[a][k]+graph[k][b])

 

문제 LIST

미래도시

전보

플로이드

정확한 순위

화성탐사

숨바꼭질