[알고리즘] 최단거리,최소신장트리,최대유통량

소개글

피보나치 힙을 사용하여 구현했습니다.
피보나치 힙도 다른 자료로 등록되어 있지만
여기에는 피보나치 힙 소스까지 함께 들어있습니다.
보고서까지 함께 포함되어 있습니다.

목차

1.개요
2.서론
3.문제접근과정
4.결과
5.토의

본문내용

2. 서론
이번 과제에서는 Graph Algorithm에서 배운 내용을 사용하여 Minimum Spanning Tree 와 Single Source Shortest Path, 그리고 Maximum Flow를 찾아보는 것이다.

① Prim's Algorithm
Prim 의 알고리즘은 Greedy 방식을 사용하여 MST를 찾는다. 임의의 노드에서 시작하여 edge 의 weight 가 가장 작으면서 이미 찾은 트리에 safe 한 edge 들을 차례로 찾아가면서 트리를 성장시켜 나가는 알고리즘이다.
Prim 의 알고리즘은 일반적으로 O(ElogV) 의 시간복잡도를 가지지만 Fibonacci Heap을 사용하면 O(E+VlogV)로 시간복잡도를 낮출 수 있다.
이 보고서에서는 Fibonacci Heap을 사용하였으며 실행결과는 각 노드와 이전 노드의 쌍으로 출력한다.
결과를 쉽게 확인할 수 있도록 Graph 에 붉은색 선으로 표시하여 보고서에 포함하였다.

참고 자료

Introduction to Algorithms

압축파일 내 파일목록

Ford/Ford.cpp
Ford/Ford.dsp
Ford/Ford.plg
Dijkstra/Dijkstra.cpp
Dijkstra/Dijkstra.dsp
Dijkstra/Dijkstra.plg
Dijkstra/fib.cpp
Dijkstra/fib.h
Prim/fib.cpp
Prim/fib.h
Prim/Prim.cpp
Prim/Prim.dsp
Prim/Prim.plg
보고서.hwp
Shortest_Path.dsw
Shortest_Path.ncb
Shortest_Path.opt

전체 목록 보기