[공학]프림 알고리즘

소개글

프림(prim)알고리즘을 이용한 최단경로 문제, c언어 소스와 발표자료입니다.

목차

알고리즘 소개
예제 소개
프로그래밍 설명
실행결과

본문내용

Prim 알고리즘은 Minimum Spanning Tree Problem (최소신장트리)을 해결하도록 고안된 알고리즘이다.
Minimum Spanning Tree Problem (최소신장트리)의 예를 들어보면, 도시계획사가 모든 도시 사이를 연결하는 자동차 도로를 계획하고 있다고 하자. 만약에 건설자금의 제한과 같은 제약이 따른다면 계획사는 건설하려는 도로의 길이를 최소로 하여 일을 추진하고 싶을 것이다. 이처럼 모든 노드가 서로 최소한의 경로로 모두 연결하는 것이 최소신장트리 문제라고 할 수 있다.

Dijkstra 알고리즘과 달리 Flag과정 행렬을 2차원 배열로 잡은 이유는 Prim알고리즘에서 몇 번 노드와 몇 번 노드가 서로 연결되어 있는지를 알아야 하는데 1차원 배열상에서는 그 결과를 알 수 없기 때문에 2차원 배열로 설정함.

참고 자료

없음