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