다익스트라 최소비용, 경로출력

#include <iostream>

#include <cstdlib>

using namespace std;

#define N 12

#define M 987654321

int cost[N+1][N+1]={

{0, 0,0,0,0,0,0,0,0,0,0,0,0},

{0, 0,7,M,1,M,M,M,M,M,M,M,M}, // from 인천

{0, 3,0,5,M,8,M,M,M,M,M,M,M}, // from 서울

{0, M,3,0,M,M,3,M,M,M,M,M,M}, //from 강릉

{0, 3,M,M,0,4,M,4,M,M,M,M,M}, //from 천안

{0, M,13,M,3,0,1,M,2,M,M,M,M}, //from 청주

{0, M,M,5,M,2,0,M,5,M,M,M,M}, //from 동해

{0, M,M,M,5,M,M,0,5,3,3,M,M}, //from 대전

{0, M,M,M,M,M,3,5,0,M,3,3,M}, //from 울진

{0, M,M,M,M,M,M,3,M,0,6,M,5}, //from 광주

{0, M,M,M,M,M,M,6,M,M,0,2,1}, //from 대구

{0, M,M,M,M,M,M,M,1,M,M,0,2}, //from 경산

{0, M,M,M,M,M,M,M,M,4,M,2,0} //from 부산

};

struct CityInfo{

string city_name;

int city_num;

};

CityInfo cities[N+1]={ "쓰레기값",0, "인천",1, "서울",2, "강릉",3, "천안",4, "청주",5, "동해",6,

"대전",7, "울진",8, "광주",9, "대구",10, "경산",11, "부산",12};

int main()

{

int j,k,nearest_node,start,end,min,i=0,count=0,

distance_of_startNode[N+1], // 정점까지의 거리

visited[N+1], //방문처리

touch[N+1];

cout<<"시작노드번호를 입력하세요.\n인천(1), 서울(2), 강릉(3), 천안(4), 청주(5), 동해(6), 대전(7) ,울진(8), 광주(9), 대구(10) ,경산(11), 부산(12) \n";

cin>>start;

cout<<"도착노드번호를 입력하세요.\n인천(1), 서울(2), 강릉(3), 천안(4), 청주(5), 동해(6), 대전(7) ,울진(8), 광주(9), 대구(10) ,경산(11), 부산(12) \n";

cin>>end;

//start=cities[1].city_num; // 시작점 입력

for(k=1;k<=N;k++) // 초기화

{

distance_of_startNode[k]=M;

visited[k]=false;

}

distance_of_startNode[start]=0; // 시작노드 -> 시작노드 거리는 0

touch[start]=0;

for(j=1;j<=N;j++)

{

min=M;

for(k=1;k<=N;k++) // 최단거리 정점을 찾는다

{

if(!visited[k] && distance_of_startNode[k]<min)

{

nearest_node=k;

min=distance_of_startNode[k];

}

}

visited[nearest_node]=true; // 최소인 정점을 방문처리

if(min==M)

{

cout<<"도달하지 못했습니다.";

return 0;

}

// nearest node 를 거쳐서 k에 이르는 거리가 지금까지의 최단 경로보다 작으면 업데이트

for(k=1;k<=N;k++)

{

if((distance_of_startNode[nearest_node]+cost[nearest_node][k])<distance_of_startNode[k])

{

distance_of_startNode[k]=distance_of_startNode[nearest_node]+cost[nearest_node][k];

touch[k]=nearest_node;

}

}

}

//for(j=2;j<=N;j++) // 도착 경로 출력

j = end;

{

cout<<cities[j].city_name;

nearest_node=j;

while(touch[nearest_node]!=0)

{

cout<<" <- "<<cities[touch[nearest_node]].city_name;

nearest_node=touch[nearest_node];

}

cout<<"\n";

}

return 0;

}

밑 end를 for문으로 바꾸면 시작노드에 대한 모든 노드의 경로를 볼 수 있다.