#include <iostream>
#include <iomanip>
using namespace std;
class Dikstra
{
public :
Dikstra(int);
void input(); // 인접-행렬 입력 및 생성
void ShortestPath(const int n, const int v); // 빠른길로 가중치를 갱신
int choose(int); // 시작~목적지 까지의 누적 길이가 가장 적은 정점을 반환
void print_route(int i , int u); // 누적 길이를 출력
void result(int v,int end); // 최종 목적지까지의 최종 경로 출력
private:
int length; // 배열의 최대길이
int **matrix; // 인접-행렬
bool *check_route; // 중복체크 배열
int *previous; // 역추적을 위한 배열
int *dist; // 거리 누적 배열
};
Dikstra::Dikstra(int n)
{
length = n;
// N 크기 배열 생성(갔던길 중복 방지를 위해)
check_route = new bool[length];
// 최단 경로의 길이 저장을 위한 배열
dist = new int[length];
// 최단경로의 역추적을 위해
previous = new int[length];
// N by N 배열 생성
matrix = new int*[length];
for(int i=0; i<length; i++)
{
matrix[i] = new int[length];
previous[i] = -1;
}
}
void Dikstra::input()
{
char ch;
int weight=0; // 가중치
int row=0 , column=0; // 행,렬
cout <<"[ 1~5000 사이의 가중치를 입력하되, 연결이 안되어있으면 '9999' 을 입력 ]" << endl;
for(row = 0 ; row < length ; row++)
{
for(column = 0 ; column < length ; column++)
{
if(column != row)
{
cout<<" vertex "<< row << " -> "<< column << " 으로의 가중치를 입력하세요 ";
while(1)
{
try
{
cout << "입력 : ";
cin >> weight;
cin.get(ch);
if( cin.fail() || isalpha(ch) || ispunct(ch) )
{
throw "정수입력에러";
cout << weight << endl;
}
else break;
}
catch(char *error)
{
cin.clear();
while((ch = cin.get()!='\n') && ch != EOF);
cout << error << endl;
continue;;
}
}
matrix[row][column] = weight;
}
if(column == row) matrix[row][column] = 0;
}
}
cout << "행렬 완성 " << endl << endl;
}
void Dikstra::ShortestPath(const int n, const int v)
{
// dist[j] (0 <= j < n) 는 v에서 j까지의 최단 경로의 길이이다.
// 간선의 길이는 matrix[i][j]의 값 이다.
for(int i = 0 ; i < n ; i++)
{// 초기화
check_route[i] = false;
dist[i] = matrix[v][i];
}
check_route[v] = true; // 시작점은 바로 S에 속해짐
dist[v] = 0 ; // 자신까지의 거리 = 0
cout<< "=======================================================================" << endl;
cout << setw(5) << "반복|" ;
cout << setw(5) << "선택정점|";
for(int i = 0 ; i < n ; i++)
cout << setw(5)<< " dist[" << i << "] ";
cout << endl;
int u = -1;
// 정점 v에서 부터의 n-1 경로를 설정
for(int i = 0 ; i < n - 2 ; i++)
{
print_route(i,u);
u = choose(n); // choose 는 check_route[w] = false 이고,
// dist[u] = minimum dist[w] 가 되는 u를 반환
check_route[u] = true;
// ====== 최단거리로 갱신 =======//
for(int w = 0; w < n ; w++)
{
if(!check_route[w] && dist[u] + matrix[u][w] < dist[w])
{
dist[w] = dist[u] + matrix[u][w];
previous[w] = u;
}
}
// ============================== //
}
}
// 누적 거리가 가장 짧은 값으로 최신화 //
int Dikstra::choose(int n)
{
int min = 9999;
int select_v = 0;
for(int w = 0 ; w < n ; w++)
{
if(check_route[w] == false && dist[w] < min)
{
select_v = w;
min = dist[w];
}
}
return select_v;
}
void Dikstra::print_route(int i, int u)
{
cout << setw(5) << i << setw(5) << u ;
for(int i = 0 ; i < length ; i++)
{
if(dist[i]==9999) cout << setw(5) <<"x";
else cout << setw(5) << dist[i];
}
cout << endl;
}
// ================= 목적지까지의 최단경로 출력 ===================
void Dikstra::result(int v,int end)
{
cout << "===================================================================================" << endl;
cout << "누적길이 : "<< dist[end] << endl;
cout <<" [최단경로]" << endl;
cout << "도착(" << end <<") <---------------------------- " << "시작(" << v <<")"<< endl;
cout << " ";
cout << end << " - ";
while(previous[end] != -1)
{
cout << previous[end] << " - ";
end = previous[end];
}
cout << v <<endl;
}
'노트 > 소스 코드' 카테고리의 다른 글
| [R] Co-occurrence Matrix (0) | 2016.02.09 |
|---|---|
| [Java] Polynomials with integer coefficients (0) | 2016.01.18 |
| [C] Multi Thread Server Example (0) | 2011.12.28 |
| [Java] Twitter Capturer (with JSON) (NOT BRUSH) (0) | 2011.12.28 |
| [C] English Morpheme Analyzer (With Lex) (0) | 2011.12.28 |
| [Java] Simple Thread Example - Horse Race (0) | 2011.12.28 |
| [C] Char, Word, Line Count (With Lex) (0) | 2011.12.28 |
| [JavaScript] Layer Popup Example (0) | 2011.12.28 |
| [Java] Notepad (0) | 2011.12.28 |
| [Java] RSS Reader (0) | 2011.12.28 |