다익스트(Dijkstra)알고리즘으로 구현한 최단거리 구하기 소스

소개

.

목차

1.문제점
2.알고리즘 설명
3.시나리오
4.소스보기
5.실행결과값

본문내용

. 문제점
- 방향그래프(Directed Graph)의 간선이 양수의 Weight를 가질 때 임의의 출발 정점에서
도착 정점까지의 경로 중 경로의 길이가 최소인 경로를 최단경로라고 정의한다.
이러한 최단경로는 도로망, 항공로 지도, 작업공정계산 등에 널리 응용된다. 최단경로는
다익스트라의 알고리즘으로 구할 수 있다.
2. 알고리즘 설명
『최단 경로 (최소비용)』 - 다익스트라
- 사용된 소스는 다익스트라 알고리즘을 이용하여 주어진 그래프에서 입력하는 임의의
출발점 s 에서부터 도착점 e 까지 최단경로와 최단경로에서 거쳐 가는 값의 합 화면에
보여줄 수 있다. 언어는 C를 사용하였고, 최단경로와 그 경로 안에서 거쳐 가는 값들의
합을 나타내기 위해 for문을 사용하였다. 갈 수 있는 경로에서 나타낸 값을 서로 비교하여,
값이 적은 부분으로 이동할 수 있도록 표시하였다. 위의 소스를 인터넷에서 참조한 거라
그런지 내용이 많이 빈약하여 보완할 점이 어느 정도 있는 것 같다. 일단 이런 형식으로
기말 과제를 할 예정이고, 차후 부족한 부분은 다른 관련 자료를 찾아서 더 보완할 것이다
4. 소스 코드 및 주석
#include
#include
#define max 10
#define distMax 50000
class Trace
{
int length[max][max]; // 길이 인접 행렬
int distance[max]; // 각 거리
bool check[max]; // 확정
bool trace[max][max]; // 경로 찾기
int tracestack[max]; // 경로 넣을 곳
public:
Trace();
int TracePath(const int, const int);// 경로 추적 함수
void ShortestPath(const int, const int,const int);// 최소비용 찾기
int choose(const int);// 확정되지 않은 정점 중 가장 비용이 적은 것.

참고자료

· 없음