다익스트라 알고리즘

[최단경로] 다익스트라 - Python

최단경로 알고리즘 그래프 상에서 가장 짧은 경로를 찾는 알고리즘 최단경로를 찾는 알고리즘으로는 다익스트라 알고리즘과 플로이드 워셜 알고리즘, 벨만포드 알고리즘이 있다 종류 한 지점에서 다른 특정 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 모두 구하기 등이있음 표현 방법 그래프로 표현하며 각 지점은 그래프에서 노드로 표현되고, 지점간 연결된 도로는 그래프에서 간선으로 표현됨 다익스트라 알고리즘 '단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드'를 선택한 뒤에 그 노드를 거쳐가는 경우를 확인해 최단 거리를 갱신하는 방법 우선순위 큐를 이용해 소스코드를 작성해야 효율적이다 역할 : 한 지점에서 다른 모든 지점까지의 최단 경로를 계산합니다 음의간선(0보다 작은 값을 가지..