벨만포드

[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra), 벨만-포드 (Bellman-Ford) (자바/Java)

목차 최단 경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라 (dijkstra): 음의 가중치 허용x 벨만-포드(Bellman-Ford) : 음의 가중치 허용o 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 1. Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 탐욕 기법을 사용 - 프림 알고리즘과 유사 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재 이때 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지으 ㅣ최단 경로로 구성됨 s→t = s→x + x→t 시간복잡도 : O(ElogV) 과..