코테
[Python] 이코테 Chapter 09 최단 경로 이론정리
최단경로 알고리즘은 BFS, DFS, 그리디 등의 알고리즘을 이용하여 어떤 그래프 내의 한 노드에서 다른 노드까지의 최단 경로를 찾는 알고리즘이다. 최단경로 알고리즘은 보통 3가지의 풀이법으로 풀린다. 다익스트라 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 이다. 1. 다익스트라 알고리즘 일단 기본적으로 최단경로 알고리즘은 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 여기에서 추가로 다익스트라 알고리즘은 '음의 간선'이 없을 경우에 정상 동작한다. 다익스트라 알고리즘은 시작노드 기준으로 시작노드와 가까운 노드부터 최단경로를 구하고 지금까지 구한 최단경로를 가지고 다음 노드들의 최단경로를 구하는 알고리즘이다. 다이나믹..
