#include <iostream>
#include <iomanip> // printf의 %-10s 같이 동일한 간격 출력 위해
#include <string>
#include <cstdlib>
using namespace std;
class MatrixWDigraph
{
private:
string cityName[8];
int length[8][8]; //인접 도시와의 비용
int dist[8]; //시작 정점에서의 최단 경로
bool s[8]; //최단 경로를 찾으면 s[i]는 true
//갱신된 정점의 비용 출력
void displayValues(int u)
{
char before;
cout << right; //오른쪽 정렬
for (int i = 0; i < 8; i++)
{
before = ' ';
if (i == u)
before = '[';
else if (i - 1 == u)
before = ']';
cout << before << setw(4); //적당한 간격 유지
if (dist[i] == INT_MAX) //가는 경로가 없을 경우
cout << "+∞";
else
cout << dist[i];
}
if (u == 7)
cout << ']';
cout << endl;
}
public:
MatrixWDigraph()
{
cityName[0] = "Los Angeles";
cityName[1] = "San Francisco";
cityName[2] = "Denver";
cityName[3] = "Chicago";
cityName[4] = "Boston";
cityName[5] = "New York";
cityName[6] = "Miami";
cityName[7] = "New Orleans";
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
length[i][j] = INT_MAX; //큰 숫자로 초기화
length[i][i] = 0; //자기자신은 0
}
//Figure 6.27 그대로
length[4][3] = 1500; //Boston->Chicago
length[4][5] = 250; //Boston->New York
length[3][2] = 1200; //Chicago->Denver
length[5][6] = 900; //New York->Miami
length[5][7] = 1400; //New York->New Orleans
length[6][7] = 1000; //Miami->New Orleans
length[7][0] = 1700; //New Orleans->Los Angeles
length[2][1] = 800; //Denver->San Francisco
length[1][0] = 300; //San Francisco->Los Angeles
}
/*
dis[j](0<=j<n)는 n개의 정점을 가진 방향그래프 G에서
정점 v로부터 정점 j까지의 최단 경로 길이로 설정됨.
간선의 길이는 length[i][j]
*/
void ShortestPath(const int n, const int v)
{
int u; //최단 경로 정점
string selectS; //검색된 최단 경로를 누적
for (int i = 0; i < n; i++)
{
s[i] = false;
dist[i] = length[v][i];
}
s[v] = true;
dist[v] = 0;
selectS = v + 48; //아스키코드
//머리글 출력
cout << ">>" << cityName[v] << "에서 출발하는 최단 경로 <<" << endl << endl;
cout << left << "반복 " << setw(21) << "S(최단 경로 도시)" << " ";
for (int i = 0; i < n; i++)
cout << " " << i << " ";
cout << endl << "---- --------------------- ---- ---- ---- ---- ---- ---- ---- ----" << endl;
//초기값 출력
cout << "초기 " << setw(21) << "-";
displayValues(v);
//정점 v로부터 n-1개의 경로를 결정
for (int i = 0; i < n-1; i++)
{
u = Choose(n); //s에서 true가 없는 최단 경로 정점
s[u] = true; //s[u]는 새로운 최단 경로이므로 true
//최단 경로 정점이 아닌 정점 중에서 최단 경로를 찾아서 갱신
for (int w = 0; w < n; w++)
if (!s[w] && length[u][w] != INT_MAX&&dist[i] + length[u][w] < dist[w])
dist[w] = dist[u] + length[u][w];
//반복 실행에 따른 중간 결과 출력
cout << right << setw(4) << i + 1 << " ";
cout << left << setw(20) << selectS << " ";
displayValues(u);
//선택한 도시 기호를 selectS에 누적 기록
selectS.append(",");
selectS += u + 48;
}
cout << " " << left << selectS << endl;
cout << "-->" << cityName[v] << "에서 각 도시별 최단 경로\n";
for (int i = 0; i < n; i++)
if (v != i)
cout << " " << left << i << " " << setw(15) << cityName[i] << ":" << right << setw(4) << dist[i] << endl;
cout << endl;
}
//dist[u]=minimum dist[w]인 u를 반환
int Choose(const int n)
{
int min = INT_MAX; //기호가 있는 최대 정수 값으로 초기화
int u = -1; //반환할 최단 경로
//최단 경로를 찾지 못한 도시 중에서 최단 경로를 찾는다
for (int w = 0; w < n; w++)
if (!s[w] && dist[w] < min)
{
min = dist[w];
u = w;
}
return u;
}
//도시의 기호와 이름을 한 줄에 4개씩 출력
void displayCityName()
{
for (int i = 0; i < 8; i++)
{
cout << left << '[' << i << "]" << setw(15) << cityName[i];
if ((i + 1) % 4 == 0)
cout << endl;
}
cout << endl;
}
};
int main(void)
{
MatrixWDigraph mwd;
mwd.displayCityName();
cout << "Figure 6.5는 단방향 그래프이므로 무조건 Boston에서 시작" << endl;
mwd.ShortestPath(8, 4);
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, http://blog.naver.com/PostView.nhn?blogId=mikekim73&logNo=50023239984
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*코드는 http://blog.naver.com/PostView.nhn?blogId=mikekim73&logNo=50023239984를 거의 그대로 작성했습니다.
*최단경로 표를 출력하는데 한칸씩 밀리는 문제는 시간 나는대로 고치도록 하겠습니다.
*그래프 관련 개념이 어렵게 느껴지는데 책의 설명이 빈약하게 느껴집니다.
*쉽게 풀어쓰는 c++ 자료구조에 자세히 설명되어있다면 그 문제는 혼자 풀도록 하겠습니다!