1. 문제 이 문제는 주어진 그래프에서 '사이클'을 찾는 문제이다. 특히 1번 정점을 지나는 '사이클' 만 찾으면된다는 것이다. 다른 곳에서 생기는 사이클은 전부 무시해도 된다는 것이다. 하지만 이 문제는 한번 꼬아서 최대와 최소 즉 양의 무한대와 음의 무한대일 경우도 찾아야하는 것이다. 2. 벨만-포드 알고리즘 벨만-포드 알고리즘은 relax를 |V|번하게되면 그래프에 음수사이클의 여부를 알 수 있다. 이 알고리즘을 조금 변형하여 V번째 완화에서 만약 성공하면 시작점부터 완화가 발생한 지점까지 갈 수 있는지 확인하고 완화가 발생한 지점에서 목적지까지 갈 수 있는지 또 확인해야한다. 이는 0번에서 1번까지 도달하는것을 제외한 모든 사이클을 무시하게 해준다. 코드는 다음과 같다 이 코드는 최대 최소를 한번..

1.플로이드의 모든 쌍 최단 거리 알고리즘 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구해야 할 때도 있다. 이런 문제를 해결하는 가장 간단한 방법은 각 정점을 시작으로 다익스트라 알고리즘을 반복해서 실행하는 것이다. (음수가 있다면 벨만-포드 알고리즘 사용) 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 배열 dist[][]를 계산한다. (동적 계획법) 이 배열의 원소 dist[u][v]는 정점 u에서 v로 가는 최단 거리를 나타낸다. 2. 정점의 경유점들 두 정점 u, v를 잇는 어떤 경로가 있다고 하자 이 경로는 u, v를 지나가고 다른 정점 또한 지나갈 수 있다. u와 v를 직접 연결하는 간선이 없거나, 다른 정점을 경유해서 가는 편이 전체 경로가 더 짧아질 수 있기 때문이다..

1. 벨만 포드 알고리즘(Bellman-Ford) 다익스트라는 한 시작점의 최단 거리들을 구하는 알고리즘이지만 음수 간선이 있는 경우 정당성이 보장되지 않는다. 벨만 포드 알고리즘은 다익스트라 알고리즘과 똑같은 단일 시작점 최단 경로 알고리즘이다. 이것은 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며, 음수 사이클의 여부 또한 알 수 있다. 벨만-포드 알고리즘은 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 그러므로 수행 과정에서 각 정점까지의 최단 거리의 상한을 담은 배열 upper[]을 유지해야한다. 이 값은 알고리즘이 진행됨에 따라 점점 줄어들고, 알고리즘이 종료할 때는 실제 최단 ..

1. 문제 이 문제는 여러 소방서에서 불난집까지 가는 최단 거리들을 찾는 것이다. 이것은 불난집을 여러번 다익스트라를 돌려서 가장짧은 소방서를 찾으면 해결되지만 이 문제의 의도는 아니다. (소방서를 기준으로 돌리거나 플로이드의 모든 쌍 최단 경로 알고리즘(O(V^3))을 이용하여 풀 수 도 있지만 느리다) 2. 모든 소방서를 하나로 이 문제는 모든 소방서를 한 소방서에 합치면 다익스트라 한번에 해결 할 수 있다. 다음은 모든 입력이 주어지고나서 첫번째 소방서에다가 하나로 합친 그래프를 만들고 문제를 해결하는 코드이다. 책에서는 인덱스 0 인 임의의 정점을 만들어서 이를 가중치가 0 으로 소방서를 전부 이었다. 이렇게하면 모든 소방서에서 동시에 다익스트라를 수행하는것과 같다. 1 2 3 4 5 6 7 8 ..

1. 다익스트라 문제 이 문제는 간단한 다익스트라 문제이다. 이 문제의 핵심은 정수의 거리가 아닌 실수인 노이즈의 증폭도라는 것이다. 따라서 간선을 지나가면서 가중치를 더하는게 아니라 곱을 하는 것이다. 2. 책의 풀이 책에서는 곱을 로그의 합으로 변환해서 문제를 해결하였다. 로그의 합의 최소를 구하고 exp()만 해주면 답을 구할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #inc..

1. 최단 경로 문제 (shortest path problem) : 가중치 있는 그래프 최단 경로 문제란 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제로, 그래프의 응용 문제 가운데 가장 유용하고 널리 사용된다. 가중치가 없는 그래프에 대한 최단 경로는 BFS를 사용하면 되므로 여기서는 가중치 있는 그래프에 대한 알고리즘을 다룬다. 이 알고리즘들은 '최단 경로'를 구성하는 정점들의 목록을 구해주는 것이 아니라 '최단 경로의 길이'를 찾아 주는 것들이다. 실제 경로를 얻어내려면 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내는 코드를 작성해야한다. 다양한 그래프의 종류와 특성에 따라 알고리즘의 효율성이 달라지기 때문에 많은 경로 알고리즘이 존재한다...