사각형 map 형식

# paths = [path, path, ... , [a, b, cost], path]
# n : 노드의 개수
# 예시
#   1  2  3 
# 1  0 c1 c2
# 2 c1  0 c3
# 3 c2 c3  0
def path_node_graph(paths, n):
    graph = [[0 for _ in range(n)] for _ in range(n)] # 모든 거리 0으로 초기화
    for path in paths:
        a, b, cost = path
        graph[a-1][b-1] = cost
				graph[b-1][a-1] = cost
    return graph

dict 형태

# paths = [path, path, ... , [a, b, cost], path]
# n : 노드의 개수
# 예시
# { 
#   1 : {2 : 3},
#   2 : {1 : 3, 
#        3 : 5}
# }
def dic_graph(paths, n):
    dic = {}
    for path in paths:
        a, b, cost = path
        if a not in dic:
            dic[a] = {b : cost}
        else:
            dic[a].update({b : cost})
            
        if b not in dic:
            dic[b] = {a : cost}
        else:
            dic[b].update({a : cost})
    return dic

Algorithm

다익스트라의 경우 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 이후 해당 노드를 거쳐가는 경로를 확인하며 최단 거리 테이블을 갱신하는 방식으로 동작한다.<--> 플로이드 워셜 알고리즘 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만, 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다!