[8주차] 최단 경로

- 플로이드 와샬 알고리즘 : 모든 노드를 방문하는 최단 경로

 

- 다익스트라 알고리즘 : 특정 노드에서 다른 노드까지의 최단 경로

 

<플로이드 와샬>

values = [2**31-1 for i in range(n)] # 비용 배열, 거리 배열 선언
visited = [False for i in range(n)]  # 0번 노드를 시작점으로 설정

start = 0
vistied[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[0]], 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 += refer
    
    # 해당 노드 방문 여부 체크
    for i in range(n):
	    if(visited[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 # 0번 노드를 시작점으로 설정
cost[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:
    	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[v1] = min(cost[v1], cost[v2] + c)