[파이썬][알고리즘]최단 경로 Shortest Path

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

0보다 작은 값을 가지는 간선이 없을 때 정상적으로 작동

특정한 노드에서 출발하여 다른 노드로 가는 각자의 최단 경로를 구해주는 알고리즘

 

구현하는 방법

1. 구현하기 쉽지만 느리게 동작하는 코드

2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

 

 

import sys
input = sys.stdin.readlin
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("INFINITY")
    else:
    	print(distance[i])
        
        

 

 

*이 글은 [이것이 취업을 위한 코딩테스트이다 with 파이썬]을 혼자 공부하며 정리한 글입니다.