[Algorithm] 최단경로찾기 - 플로이드 와샬 & 다익스트라

n = 6  # 노드의 총 개수
costs = [  # [노드a, 노드b, a에서 b로 이동하는 비용]
    [0,1,7],
    [0,4,3],
    [0,5,10],
    [1,2,4],
    [1,3,10],
    [1,4,2],
    [1,5,6],
    [2,3,2],
    [3,4,11],
    [3,5,9]    
]

def solution(costs):
    values = [2**31-1 for _ in range(n)]  # 비용 배열 : int의 최대값으로 초기 설정
    visited = [False for _ in range(n)]  # 방문 배열 : False로 초기 설정
    answer = 0

    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:   # i[0]에서 i[1]로 가는 경우
                values[i[1]] = min(values[i[1]], i[2])
            if visited[i[0]] == False and i[1] == start:   # i[1]에서 i[0]로 가는 경우
                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  # 현재 노드를 i로 이동한 후 while문 재실행
                break            

	return answer

import sys

n = 6
costs = [
    [0,1,7],
    [0,4,3],
    [0,5,10],
    [1,2,4],
    [1,3,10],
    [1,4,2],
    [1,5,6],
    [2,3,2],
    [3,4,11],
    [3,5,9]    
]

def solution(costs):
    values = [sys.maxsize for _ in range(n)]  # 비용 배열 : int의 최대값으로 초기 설정
    visited = [False for _ in range(n)]  # 방문 배열 : False로 초기 설정
    
    start = 0  # 시작 노드
    values[start] = 0   
    
    while False in visited:
        # 탐색하지 않은 노드 찾기
        checkLoc = -1  # 탐색할 노드를 담을 변수
        checkValue = sys.maxsize  # 해당 노드까지 가는 비용을 담을 변수
        for i in range(n):
            if visited[i] == False and values[i] < checkValue:  # for문을 돌면서 방문하지 않은 노드 중 비용 최솟값을 갖는 노드를 선택
                checkLoc = i  
                checkValue = values[i]  
                       
        # 탐색하지 않은 노드가 없다면(for문 다 돌았는데 checkLoc가 바뀌지 않음) while문 종료
        if checkLoc == -1:
            break       
        
        # 경로 완전탐색으로 비용배열 갱신
        visited[checkLoc] = True
        for v1, v2, c in costs:
            if v1 == checkLoc and visited[v2] == False:   # v1에서 v2로 가는 경우
                values[v2] = min(values[v2], values[v1]+c)
            if v2 == checkLoc and visited[v1] == False:   # v2에서 v1로 가는 경우
                values[v1] = min(values[v1], values[v2]+c)
        
    return values