justgo_developer

최소 스패닝 트리(Minimum Spanning Tree, MST)란? 최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미한다. 이때, 간선의 가중치 합을 최소로 하며 연결하여야 한다. 이때 생성되는 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지 못한다. Generic MST 알고리즘- 어떤 MST의 부분집합 A에 대해서 A∪{(u,v)}도 역시 어떤 MST의 부분집합이 될경우 에지(u,v)는 A에 대해서 안전하다(safe)고 한다.- Generic MST 알고리즘1. 처음에는 A는 공집합이다.2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.3. 에지의 개수가 n-1개가 ..

플로이드 워셜 알고리즘(Floyd-Warshall) All-pairs 문제 그래프에서 모든 정점 사이의 최단경로 및 최단거리를 구하는 알고리즘 동적계획법 접근으로, 그래프 상의 모든 두 정점을 잇는 경로의 최단거리를 구한다.여기에 경유지를 기록하면 최단거리 경로까지 구할 수있다.- 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.- 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다. 음수사이클이 없는 그래프라면 음수 가중치가 있어도 동작

벨만-포드 알고리즘(Bellman-Ford Algorithm) single source 문제 음수 가중치가 있고, 음수 사이클이 없는 그래프에서 한정점에서 다른 모든 정점까지의 최단경로 및 거리를 구하는 알고리즘음수사이클이 있으면 무한히 사이클을 루프할수 있어서 최단경로를 구할수 없다.단 벨만포드알고리즘의 장점은 그래프내에 음수사이클이 있음을 판단할수 있다. 1. 시작점을 제외한 모든 정점들을 최단거리를 무한대로 설정2. 그래프 모든 간선에 대해3. 정점 A에서 B로의 방향을 가지고 있는 각 간선에 대해현재 정점 B까지의 거리가 정점 A까지의 거리 + 현재 간선의 거리의 합보다 클경우정점 B의 경로와 거리를 갱신해준다.4. 이들 경로와 거리의 갱신이 일어나지 않을때까지 반복한다.만약 정점의 수 만큼의 시..