//dynamic programming to seek shortest route
#include <iostream.h>
//this program is edited by 200624101101杨振平
//this paper's edited time is DEC 3th,2008
//define the count of nodes less 1
#define N 15
//define a constant
#define NoEdge -1
//initial a graph
int a[N+1][N+1]=
{
//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
{ 0, 5, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},//0
{-1, 0,-1, 1, 3, 6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},//1
{-1,-1, 0,-1, 8, 7, 6,-1,-1,-1,-1,-1,-1,-1,-1,-1},//2
{-1,-1,-1, 0,-1,-1,-1, 6, 8,-1,-1,-1,-1,-1,-1,-1},//3
{-1,-1,-1,-1, 0,-1,-1, 3, 5,-1,-1,-1,-1,-1,-1,-1},//4
{-1,-1,-1,-1,-1, 0,-1,-1, 3, 3,-1,-1,-1,-1,-1,-1},//5
{-1,-1,-1,-1,-1,-1, 0,-1, 8, 4,-1,-1,-1,-1,-1,-1},//6
{-1,-1,-1,-1,-1,-1,-1, 0,-1,-1, 2, 2,-1,-1,-1,-1},//7
{-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1, 1, 2,-1,-1,-1},//8
{-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1, 3, 3,-1,-1,-1},//9
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1, 3, 5,-1},//10
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1, 5, 2,-1},//11
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0, 6, 6,-1},//12
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1, 4},//13
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0, 3},//14
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0} //15
};
//define the array to store the add short route
int c[N+1][N+1];
//define the array to store the positiong of the add short route
int kay[N+1][N+1];
//main function
void main()
{
//define Allpairs function
void Allpairs(int n);
//define OutputPath function
void OutputPath(int i,int j);
//call Allpairs function
Allpairs(N);
//print the array of storing the add short route
for(int i=0;i<=N;i++)
{
for(int j=0;j<=N;j++)
cout<<c[i][j]<<" ";
cout<<endl;
}
//call OutputPath function
OutputPath(0,N);
}
//implement Allpairs function
void Allpairs(int n)
{
//to seek the shortest route all the points
//to all the i and j，to calculate c [ i ] [ j ] and k a y [ i ] [ j ]
//initial c [ i ] [ j ] = c（i，j，0）
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++) {
c[i][j] = a[i][j];
kay[i][j] = 0;
}
for (i = 0; i <= n; i++)
c[i][i] = 0;
// to calculate c[i][j] = c(i,j,k)
for (int k = 0; k <= n; k++)
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++) {
int int1 = c[i][k];
int int2 = c[k][j];
int int3 = c[i][j];
if (int1 != NoEdge && int2 != NoEdge && (int3 == NoEdge || int1 + int2 < int3)) {
c[i][j] = int1 + int2;
kay[i][j] = k;}
}
}
//implement outputPath function to output shortest route
void outputPath(int i,int j)
{
// print the route from i to j
if (i == j) return;
if (kay[i][j] == 0) cout << j << ' ';
else {outputPath(i,kay[i][j]);
outputPath(kay[i][j],j);}
}
//implement OutputPath function
void OutputPath(int i,int j)
{
// print the shortest route from i to j
if (c[i][j] == NoEdge) {
cout << "there is no path from " << i << " into " << j << endl;
return ; }
cout << "the path is" << endl;
cout << i << ' ';
//call outputPath function
outputPath(i,j);
cout << endl;
}