최단경로 다익스트라 알고리즘 구현 소스 입니다

본문내용

"
<< "출발점과 도착점이 같으면 종료합니다.\n출발점의 번호를 입력하십시오 : ";
cin >> start_node;// 출발점 번호 입력
path[0] = start_node; // 출발점을 path[0] 에 기록
cout << "도착점의 번호를 입력하십시오 : ";
cin >> end_node;// 도착점 번호 입력
if (start_node<0 || start_node>8 || end_node<0 || end_node>8 || start_node==end_node){
cout << "번호 선택을 잘못 하였습니다.\n";
exit(1);
}
}
void dijkstra(){
distance();
print_distance();
exit(1);
}
void distance(){
shortest_distance[start_node] = 0;
int k;
for (int i=0; i<9; i++){
minimum = p;
for (int j=0; j<9; j++){
if (node_check[j]==0 && shortest_distance[j] < minimum){
k = j;
minimum = shortest_distance[j];
}
}
node_check[k] = 1;
if (minimum==p){
break;
}
for (j=0; j<9; j++){
if (shortest_distance[j] > shortest_distance[k] + distance_adj_matrix[k][j]){
shortest_distance[j] = shortest_distance[k] + distance_adj_matrix[k][j];
path_check[j] = k;
}
}
path_save(k,i);
if(node_check[end_node]==1){
break;
}
}
}
void path_save(int k,int i){
path[i] = k;
k=path_check[k];
}
void print_distance(){
cout << "Total of Distance : " << shortest_distance[end_node] << endl;
cout << "Path of Distance : ";
int i=0;
while (path[i] !=p){
cout << path[i];
if (path[i+1] != p){
cout << " -> ";
}
i++;
}
cout << endl;
}
3. 실행 결과

키워드

최단경로,   ShortestPath,   다익스트라,   Dijkstra,   알고리즘,   소스