[Python]다익스트라(Dijkstra)

플로이드 와샬 알고리즘

• 모든 노드를 방문하는 최단 경로

values=[2**31-1 for i in range(n)] #비용배열 
visited=[False for i in range(n)] #방문배열
start=0 #0번 노드를 시작점으로 설정 
visited[start]=True
values[start]=0
while False in visited: #방문하지 않은 노드가 있다면 
	for i in costs: #노드 완전 탐색으로 비용배열 거리 값 최소화 
    	if(visited[i[1]]==False and i[0]==start):
        	values[i[1]]==min(values[i[1]],i[2])
        if(visited[i[0]]==False and i[1]==start):
        	values[i[0]]==min(values[i[1]],i[2])
    refer=2**31-1
    for i in range(n): #방문하지 않은 노드 중 최소 비용 노드 위치 탐색 
    	if(visited[i]==False and values[i]!=0):
        	refer=min(refer,values[i])
    answer = answer+refer
    for i in range(n): #해당 노드 방문 여부 체크 
    	if(visited[i[i]]==False and values[i]==refer):
        	visited[i]=True
            start=i
            break

다익스트라 알고리즘

• 특정 노드에서 다른 노드까지의 최단 경로

visited=[False for _ in range(n)] #방문배열
cost=[sys.maxsize for _ in range(n)] #비용배열 
visited[0]=True
cost[0]=0 #0번 노드를 시작점으로 설정 
length=len(visited)
while False in visited: #방문하지 않은 노드가 있다면 
	checkLoc=-1
    checkValue=sys.maxsize
    for i in range(length): #방문하지 않은 지역 중 최솟값 찾기 
    	if(visited[i]==False and cost[i]<checkValue):
        	checkLoc=i
            checkValue=cost[i]
    if checkLoc==-1: #방문하지 않은 노드가 없다면 while반복문 탈출 
    	break
    visited[checkLoc]=True
    for v1,v2,c in costs:#경로 완전탐색으로 비용 배열 수정 
    	if v1==checkLoc and visited[v2]==False:
        	cost[v2]=min(cost[v2],cost[v1]+c)
        if v2==checkLoc and visited[v1]==False:
        	cost[v2]=min(cost[v1],cost[v2]+c_