[이코테] 최단 경로_플로이드 (python)

나의 풀이

1. 플로이드 워셜 알고리즘

n = int(input()) # 도시의 개수 n
m = int(input()) # 버스의 개수 m
bus = [list(map(int, input().split())) for _ in range(m)] # 도시 사이를 있는 버스 비용 list

INF = int(1e9) # 무한을 의미하는 10억 설정

# 도시간 버스 비용을 담을 2차원 list. 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에게 가는 비용 = 0 으로 초기화
for i in range(1, n + 1):
	graph[i][i] = 0
    
# 모든 버스 연결 정보를 저장
# i[0]: 출발 도시, i[1]: 도착 도시, i[2]: 버스 비용
# 도시간 버스가 중복되는 경우, 더 적은 비용으로 저장
for i in bus:
	# graph[i[0]][i[1]]: 기존에 graph에 저장된 비용, i[2]: 방금 꺼낸 비용
	if graph[i[0]][i[1]] > i[2]: # 방금 꺼낸 비용이 더 저렴할 경우
		graph[i[0]][i[1]] = i[2] # 새로운 값으로 갱신
		
# 플로이드 워셜 알고리즘 수행
# 점화식: D_ab = min(D_ab, D_ak + D_kb)
for k in range(1, n + 1):
	for a in range(1, n + 1):
		for b in range(1, n + 1):
			# a에서 b로 가는 비용
			# =a에서 b로 가는 비용과 a에서 k를 거쳐 b로 가는 비용 중 적은 비용
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
for a in range(1, n + 1):
	for b in range(1, n + 1):
		# a에서 b로 갈 수 없는 경우, 0을 출력
		if graph[a][b] == INF:
			print(0, end = ' ')
		else: # a에서 b로 가는 버스 비용 출력
			print(graph[a][b], end = ' ')
	print() # 줄 바꿈

• 다시 풀어본 결과, 아랫부분만 이렇게 수정

for a in range(1, n + 1):
	for b in range(1, n + 1):
		# a에서 b로 갈 수 없는 경우, 0을 출력해야함
		if graph[a][b] == INF:
			graph[a][b] = 0
    
for i in range(1, n + 1):
	print(*graph[i][1:])