"최단 경로"란 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 이번에는 DFS, BFS와는 별개로 최단경로에 관련하여 "다익스트라"와 "플로이드 워셜" 알고리즘에 대하여 알아보겠다. DFS, BFS와 차별점은 "간선의 값이 존재하며, 간선값에 따라 경로가 달라진다는 점이다" 그렇기에 GPS에서 소프트웨어의 기본 알고리즘으로 채택되는 중요한 개념이다. 먼저 "다익스트라" 알고리즘부터 알아보겠다. 1. 다익스트라 알고리즘 특정한 노드에서 출발하여 각 다른 노드까지의 최단 경로를 구해주는 알고리즘 다만, 음의 간선이 없을때 정상작동이 된다. 이때, 최단 거리 테이블 개념이 사용된다. import heapq import sys INF = int(1e9) input = sys.stdin.readline..
