최단 경로 구하는 알고리즘
최단 경로를 구하는 알고리즘은 크게 두 가지로 나누어볼 수 있다. 음의 경로를 갖는 그래프에서의 알고리즘과 그렇지 않은 그래프에서의 알고리즘. 음의 경로를 갖지 않는 그래프에서의 최단 경로 알고리즘은 또 2가지 문제로 나누어 볼 수 있다. 가중치가 1 또는 0인 그래프에서의 최단경로 알고리즘과 다른 가중치도 가지는 그래프에서의 최단 경로 알고리즘 가중치가 1또는 0인 그래프는 dfs나 bfs알고리즘을 통해 최단 경로를 알 수 있다. 가중치를 다른 수도 가지는 그래프에서의 최단 경로 알고리즘은 다시 아래와 같이 4가지 문제로 나누어 볼 수 있다. 1. 하나의 출발지, 하나의 도착지(single source to single destination problem) 2. 하나의 출발지, 여러개의 도착지(sing..
2019.10.29