1. 문제 이 문제는 이미 연결된 집합을 한 정점으로 표현하여 최소 스패닝 트리를 구하는 문제이다. 이 문제의 핵심은 연결된 집합을 한 정점으로 어떻게 표현할 것인가에 있다. 2. 유니온 파인드 : 크루스칼 알고리즘 이미 연결된 집합을 유니온-파인드 자료구조로 표현하여 각 집합사이의 최소 거리를 구하려면 많이 복잡하다. 이를 간결하게 구현하려면 소방차 문제에서 그랬듯이 임의적인 방법이 필요하다. 그러므로 책에서는 연결된 정점끼리 이어지는 간선의 가중치를 0으로 설정해서 항상 이 간선을 선택하게끔 하였고 가중치가 0이므로 추가되는 가중치의 합을 구할 수 있게 하였다. 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 ..

1. 최소 스패닝 트리(Minimum Spanning Tree) 외판원 문제 휴리스틱에서나 각종 그래프의 탐색 알고리즘, 최단 경로 알고리즘에서 경로를 찾는데에 사용했었다. 어떤 무향 그래프의 스패닝 트리(Spanning Tree)는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야한다. 트리 형태라는 것은 선택된 간선들이 사이클을 이루지 않는다는 것을 의미하며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 것을 의미한다. 또한 그래프안에 여러 개의 스패닝 트리가 있다. 이런 스패닝 트리 중에서 가중치의 그래프의 스패닝 트리 중 가중치 합이 가장 작은 트리를 찾는 문제를 최소 스패닝 트리 문제(Minim..

1. 문제 새로 건설할 당위성이 있다: 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결됨. 두 도시를 오가는 데 걸리는 시간이 단축 되어야함 N년간 하나씩 고속도로를 건설할때 이들 중 몇 개가 의미가 없는지 계산하여라 2. 플로이드 n번 역시 간단한 풀이는 그냥 건설할때마다 플로이드를 수행하는 것이다, 하지만 이는 시간초과로 문제를 시간안에 해결할 수 없다. 또다른 방법은 플로이드를 계산할때 a, b 정점을 경유하는지 기록하는 것 만약 고속도로가 추가되면 이 기록을따라 a->b, b->a거리를 업데이트 시키고, b와 a에 대해서만 플로이드를 다시 수행하는 것이다. 하지만 이것은 구현도 까다롭고 복잡하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

1. 문제 이 문제는 경유점이 중요하다. 한 정점마다 경유하는지를 조사하고 그 경유점으로 인해 최소거리가 되는지 조사하는 플로이드 알고리즘을 이용하여 이 문제를 해결할 수 있다. 2. 경유점 정렬 플로이드 알고리즘에서 정점들의 추가 순서는 알고리즘의 정당성에는 영향을 미치지 않는다. 따라서 delay에 대해 정렬하고, delay가 작은것 부터 조사하게 되면 경로에서 어떤점이 최대의 delay를 가지는지 별도의 연산이 필요없게된다. (항상 추가하는 정점이 현재 최대 delay이므로) 3. 플로이드 알고리즘: 잘못된 풀이 플로이드 알고리즘을 적용시킨 처음 풀이는 다음과 같았다. 정점 w를 추가 하였을 때 adj[i][w] + adj[w][j] + delay[w] 에서 i->w 에서 생기는 딜레이와 w->j ..

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

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