최단경로_Python

특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

1. 다익스트라 알고리즘

- 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘

- 가장 비용이 적은 노드를 선택하기 때문에 '그리디 알고리즘'

- '음의 간선'이 없을 때 정상적으로 작동

- 실제 GPS 소프트웨어의 기본 알고리즘으로 채택

- 각 노드에 대한 최단거리를 리스트에 저장해서 갱신

 

다익스트라 알고리즘 소스 코드

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

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())
    graph[a].append((b,c))


def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        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]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

→ 리스트 사용보다 시간 복잡도가 줄어든다. 

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

2. 플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘

- 다익스트라 알고리즘처럼 해당 노드를 거쳐가는 경로를 확인하며 최단 거리를 갱신

- 최단 거리를 2차원 리스트에 저장

- N번의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하므로 DP로 볼 수 있다. 

 

 

플로이드 워셜 알고리즘 소스 코드

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):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

# 수행된 결과를 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

 

플로이드 워셜 알고리즘 시간 복잡도

O(N^3): 노드 N개에 대해서 N번의 단계를 반복, 각 단계마다 O(N^2)의 연산을 통해 해당 노드를 거쳐가는 모든 경로를 고려

 

---

~ 문제 풀이 ~

 

1. 미래 도시

문제 보고 알고리즘 파악하기

1. 중간에 거쳐가는 곳이 있기 때문에 각각의 노드에서의 최단거리를 알아야함

2. 노드의 개수가 100이하이므로 N^3 시간 복잡도 가능

→ 플로이드워셜 문제

 

INF = int(1e9)
N, M = map(int, input().split())

# 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 = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1


for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])


x, k = map(int, input().split())

distance = graph[1][k] + graph[k][x]

if distance >= INF:
    print("-1")
else:
    print(distance)

주의점 : 도로가 서로 연결되어 있기 때문에 a→b 와 b→a 도로를 모두 graph에 저장해야한다. 

 

2. 전보

문제 보고 알고리즘 파악하기

1. 도시 C에서 각 도시로 메세지를 보냄

2. 각 도시까지의 최단 거리를 구하고, 그 중 가장 긴 거리를 구하면 된다. 

→ 다익스트라 문제

 

import heapq

INF = int(1e9)

n,m,c = map(int, input().split())

graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    x,y,z = map(int, input().split())
    graph[x].append((y,z))


def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        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]))

dijkstra(c)


cnt = 0
check = -1
for i in range(1, n+1):
    if distance[i] != INF:
        cnt += 1
        check = max(distance[i], check)

print(cnt-1, check)

 

다익스트라 함수 짜는 걸 외우고 있어야 써먹을 수 있을 것 같다.