[Python] 최단 경로 알고리즘(1)- 개요
최단경로 알고리즘이란 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제상황 한지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 간선으로 표현함 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산합니다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않습니다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됩니다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복합니다. 알고리즘의 동작 과정은 다음과 같습니다. 1...
Python/이코테
2022. 7. 9. 20:58
