목록플로이드워셜 (1)

정리정돈

최단경로

가장 빠르게 도달하는 방법 최단 경로 (Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 문제는 보통 그래프를 이용해 표현한다. 각 지점은 그래프에서 ‘노드'로 표현되고, 지점간 연결된 도로는 그래프에서 ‘간선'으로 표현된다. 코딩 테스트에서 가장 많이 등장하는 유형의 최단경로 알고리즘은 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘 이다. 다익스트라 최단 경로 알고리즘 다익스트라(Dijkstra) 최단 경로 알고리즘은 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. ‘음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다. 현실 세계의 길..
알고리즘/개념 2022. 3. 24. 09:43
이전 Prev 1 Next 다음