[이코테] 최단 경로 알고리즘
1. 다익스트라 알고리즘 최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 내가 학교를 다닐 때 배운 알고리즘은 다익스트라 알고리즘과 플로이드 워셜 이렇게 2가지였다.(더 있는데 기억 안나는 걸 수도 있음.) 이 2가지가 코딩 테스트에서 가장 많이 등장하는 유형이라고 하니 이 2가지만 먼저 자세히 알아보자. 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음..