최단경로2 벨만포드 알고리즘 (Bellman-Ford algorithm) 벨만 포드는 최단 경로 알고리즘입니다. 하나의 특정 도시에서 다른 도시들로 가는 최단 경로, 최소비용을 구하는데 사용됩니다. 벨만 포드 알고리즘과 다익스트라 알고리즘의 차이는 간선에 음수가 있을 때 사용할 수 있는가입니다. 다익스트라 알고리즘은 간선에 음수가 있을 때 사용할 수 없습니다. (참고) 벨만 포드 알고리즘은 "최단 경로는 최대 V-1 개의 간선을 지난다."를 이용한 방법으로 간선에 음수가 있을 때도 사용할 수 있습니다. (정점을 한 번씩 지났을 때가 최대로 많은 간선을 지니는 최단 경로) 그런데 만약 최단 경로에 음수 사이클(가중치의 합이 음수여서 해당 사이클을 돌 때마다 가중치 합이 줄어드는 구간)이 존재한다면 최단 거리는 끊임없이 작아질 것입니다. 그래서 벨만 포드에서 V-1 번 간선들을 .. 2019. 9. 26. 다익스트라 알고리즘 (Dijkstra's algorithm) 다익스트라는 최단경로 알고리즘입니다. 하나의 특정 도시에서 다른 도시들로가는 최단경로, 최소비용을 구하는데 사용됩니다. 도시 i에서 j로 가는 비용이 arr[i][j]이고 도시들의 방문여부를 배열 check에 저장, 도시로 가는 최소비용을 배열 dist에 저장한다고 했을 때, 다익스트라 알고리즘은 다음과 같습니다. 1. 현재 도시(now)의 방문 여부를 체크합니다. [check[now] = true] 2. 현재 도시(now)를 거쳐 갈 수 있는 도시(next)들의 비용이 현재 저장되어 있는 비용(dist[next])보다 큰 경우 이를 갱신합니다. [ dist[next] > dist[now] + arr[now][next] => dist[next] = dist[now] + arr[now][next] ] 3... 2019. 9. 18. 이전 1 다음
