[ Python ] 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘

여러 개의 노드가 있는 그래프에서 음의 간선이 없을 때 , 방문하지 않는 노드 중 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

시간 복잡도

O(E logV) ( E : 간선의 개수 ,V : 노드의 개수 )

코드

import heapq
import sys
input = sys.stdin.readline
INF = sys.maxsize
# 노드 , 간선의 개수 및 그래프 정보 입력
N , M = map(int,input().split())
start = int(input())
graph = [[] for _ in range(N+1)]

for m in range(M):
  a , b, c = map(int,input().split())
  graph[a].append((b,c))
# 최단 거리 테이블 초기화
distance = [INF] * (N+1)

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

  while q:
  	# 현재 최단 거리 노드 꺼내기
    cost , node = heapq.heappop(q)
    # 이미 처리된 노드라면 무시
    if distance[node] < cost:
      continue
    # 현재 노드와 연결된 노드들을 확인
    for d , c in graph[node]:
      dist = cost + c
      # 현재 노드를 거쳐서 이동하는게 더 빠른 경우
      if dist < distance[d]:
        distance[d] = dist
        heapq.heappush(q,(dist,d))

dijkstar(start)

---

플로이드 워셜 알고리즘

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

시간 복잡도

O(N^3)

코드

import sys
input = sys.stdin.readline
INF = sys.maxsize
# 노드 , 간선의 개수 및 그래프 정보 입력
N , M = map(int,input().split())
# 테이블 초기화
graph = [[INF]*(N+1) for _ in range(N+1)]

for m in range(M):
  a , b, c = map(int,input().split())
  graph[a][b] = c
# 자기 자신에서 자신으로 가는 비용은 0
for n in range(1,N+1):
  graph[n][n] = 0

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

for a in range(1,N+1):
  for b in range(1,N+1):
    if graph[a][b] == INF:
      print("INF",end=" ")
    else:
      print(graph[a][b],end=" ")