최단 경로 알고리즘

최단경로 문제

• 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다.

• 다양한 문제 상황
  1. 한 지점에서 다른 한 지점까지의 최단 경로
  2. 한 지점에서 다른 모든 지점까지의 최단 경로
  3. 모든 지점에서 다른 모든 지점까지의 최단 경로

• 각 지점은 그래프에서 노트로 표현

• 지점 간 연결된 도로는 그래프에서 간선으로 표현

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

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로를 계산

• 다익스트라 알고리즘은 음의 간선이 없을 때 정상적으로 동작

• 다익스트라는 그리디 알고리즘으로 분류 -> 매 상황에서 가장 비용이 적은 노드를 선택

  동작과정

  

  

  
  
  
  

코드

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)]
visited=[False]*(n+1)
distance=[INF]*(n+1)

for _ in range(m):
   a,b,c=map(int,input().split())
   graph[a].append((b,c))

def get_smallest_node():
   min_value=INF
   index=0
   for i in range (1,n+1):
       if distance[i]<min_value and not visited[i]:
           min_value=distance[i]
           index=i

       return index

def dijkstra(start):
   distance[start]=0
   visited[start]=True
   for j in graph[start]:
       distance[j[0]]=j[1]
   for i in range (n-1):
       now=get_smallest_node()
       visited[now]=True
       for j in graph[now]:
           cost=distance[now]+j[1]
           if cost<distance[j[0]]:
               distance[j[0]]=cost

dijkstra(start)

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

다익스트라 알고리즘 특징

-> 해결방법

우선순위 큐

우선순위 큐를 이용한 다익스트라 알고리즘

코드

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)]
visited=[False]*(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[i]
          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("INF")
  else:
      print(distance[i])

플로이드 워셜 알고리즘

플로이드 워셜 동작원리

코드

INF=int(1e9)

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

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

for a in range (1,n+1):
    for b in range(1,n+1):
        if a==b:
            graph[a][b]=0

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("INF")
        else:
            print(graph[a][b])