有13个点，每个点到各点距离如下表所示：
(0,0)(1,2)(2,∞)(3,∞)(4,8)(5,∞)(6,∞)(7,∞)(8,∞)(9,4)(10,∞)(11,∞)(12,8)
(0,2)(1,0)(2,3)(3,∞)(4,∞)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,1)(11,∞)(12,∞)
(0,∞)(1,3)(2,0)(3,1)(4,∞)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,∞)(11,∞)(12,∞)
(0,∞)(1,∞)(2,1)(3,0)(4,5)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,2)(11,2)(12,∞)
(0,8)(1,∞)(2,∞)(3,5)(4,0)(5,9)(6,∞)(7,∞)(8,∞)(9,∞)(10,∞)(11,3)(12,3)
(0,∞)(1,∞)(2,∞)(3,∞)(4,9)(5,0)(6,8)(7,∞)(8,∞)(9,∞)(10,∞)(11,∞)(12,6)
(0,∞)(1,∞)(2,∞)(3,∞)(4,∞)(5,8)(6,0)(7,10)(8,1)(9,∞)(10,∞)(11,∞)(12,5)
(0,∞)(1,∞)(2,∞)(3,∞)(4,∞)(5,∞)(6,10)(7,0)(8,∞)(9,∞)(10,∞)(11,∞)(12,∞)
(0,∞)(1,∞)(2,∞)(3,∞)(4,∞)(5,∞)(6,1)(7,∞)(8,0)(9,2)(10,∞)(11,∞)(12,∞)
(0,4)(1,∞)(2,∞)(3,∞)(4,∞)(5,∞)(6,∞)(7,∞)(8,2)(9,0)(10,5)(11,∞)(12,∞)
(0,∞)(1,1)(2,∞)(3,2)(4,∞)(5,∞)(6,∞)(7,∞)(8,∞)(9,5)(10,0)(11,1)(12,∞)
(0,∞)(1,∞)(2,∞)(3,2)(4,3)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,1)(11,0)(12,∞)
(0,8)(1,∞)(2,∞)(3,∞)(4,3)(5,6)(6,5)(7,∞)(8,∞)(9,∞)(10,∞)(11,∞)(12,0)
代码：
#include<limits>
#include<queue>
using namespace std;
const int max_size = 20;
class Vertex
{
public:
Vertex();
void input(int number, int distance);
queue<int> passed_way;//用来存放源节点到该节点途径的节点下标
int output(int n);
private:
int length[max_size];
};
Vertex::Vertex()
{
for(int i=0; i<max_size; i++)
length[i] = numeric_limits<int>::max(); //int的最大值
}
void Vertex::input(int number, int distance)//给第number个赋值distance
{
length[number] = distance;
}
int Vertex::output(int n)//输出第n个值
{
return length[n];
}
#include"vertex.h"
class Digraph
{
public:
Digraph();
void set_distances(int s, int distance[]);
void get_in(Vertex v, int n);
void initial_length();
Vertex number[max_size];
int adjacency[max_size][max_size];
};
const int infinity = numeric_limits<int>::max();//int的最大值
Digraph::Digraph()
{
}
void Digraph::set_distances(int s,int distance[])//计算第s个节点到其他各个节点的最小距离，结果存放在distance中
{
int v,w;
bool found[13];//用来标记其他节点到第s个节点的最短距离是否被计算确定了
for(v=0; v<13; v++)//初始化found、distance
{
found[v] = false;
distance[v] = adjacency[s][v];//将distance的值设置为第s个节点到其节点的现有距离，不联通的设为无穷大，对自己设为0
}
found[s] = true;//当前节点s对应自己的设true，让后面寻找最短距离能避开自己
distance[s] = 0;//再次赋值确保自己对自己的距离是0
for(int i=0; i<12; i++)//一共有13个节点，循环12次，依次计算对其他节点的最小距离
{
int min = infinity;//首先将min设为无穷大
for(w=0; w<13; w++)
if(!found[w])//循环除s本身的其余各个节点，找出离s最近的点
if(distance[w] < min)//distance[w]保存当前节点到各节点（包含自己）的距离，比较循环到的节点与当前最小距离
{
v = w;//如果比当前最小距离小，那么记下这个节点的下标
min = distance[w];//更改最小值
}
found[v] = true;//循环结束后，将距离s节点最近的点v标记出来
number[v].passed_way.push(v);//将v点的vertex对象中passed_way队列 存放进v点下标
for(w=0; w<13; w++)
if(!found[w])//循环除s本身和离s最近的点v 除外的其余各点
if(min + adjacency[v][w] < distance[w])//s到v的距离 + v到除s和v本身以外的其余点w的距离 如果该距离小于 s到w的距离（不联通的距离是无限大）
{
if(adjacency[v][w] != infinity)//如果v到w联通
{
distance[w] = min + adjacency[v][w];//更改s到w的距离
number[w].passed_way = number[v].passed_way;//将v点的vertex对象中的passed_way赋值给w点的vertex对象中的passed_way（passed_way是可变长度队列）
}
}
//for循环内的两个循环，第一个for找到距离s点最近的点v；第二个for计算有了v之后，其他节点到s距离的更新
}
}
void Digraph::get_in(Vertex x, int n)
{
number[n] = x;
}
void Digraph::initial_length()
{
for(int i=0; i<max_size; i++)
for(int j=0; j<max_size; j++)
adjacency[i][j]=number[i].output(j);
}
#include"digraph.h"
#include<iostream>
#include<string>
using namespace std;
int main()
{
Vertex a,b,c,d,e,f,g,h,i,j,k,l,m;
a.input(0,0),a.input(1,2),a.input(4,8),a.input(9,4),a.input(12,8);
b.input(0,2),b.input(1,0),b.input(2,3),b.input(10,1);
c.input(1,3),c.input(2,0),c.input(3,1);
d.input(2,1),d.input(3,0),d.input(4,5),d.input(10,2),d.input(11,2);
e.input(0,8),e.input(3,5),e.input(4,0),e.input(5,9),e.input(11,3),e.input(12,3);
f.input(4,9),f.input(5,0),f.input(6,8),f.input(12,6);
g.input(5,8),g.input(6,0),g.input(7,10),g.input(8,1),g.input(12,5);
h.input(6,10),h.input(7,0);
i.input(6,1),i.input(8,0),i.input(9,2);
j.input(0,4),j.input(8,2),j.input(9,0),j.input(10,5);
k.input(1,1),k.input(3,2),k.input(9,5),k.input(10,0),k.input(11,1);
l.input(3,2),l.input(4,3),l.input(10,1),l.input(11,0);
m.input(0,8),m.input(4,3),m.input(5,6),m.input(6,5),m.input(12,0);
Digraph map;
map.get_in(a,0);
map.get_in(b,1);
map.get_in(c,2);
map.get_in(d,3);
map.get_in(e,4);
map.get_in(f,5);
map.get_in(g,6);
map.get_in(h,7);
map.get_in(i,8);
map.get_in(j,9);
map.get_in(k,10);
map.get_in(l,11);
map.get_in(m,12);
map.initial_length();
int array[13];
int x = 0;//设下标为0的是源点
map.set_distances(x, array);
for(int t=0; t<13; t++)
{
if(t != x)//循环除x以外的点
{
cout<<"The shortest path "<<"From place "<<x<<" to "<<t<<"is："<<x<<"-";//从x到t的最短路径是
while( map.number[t].passed_way.front() != t )
{
cout<<map.number[t].passed_way.front()<<"-";
map.number[t].passed_way.pop();
}
cout<<t<<endl;;
cout<<"The total length is："<<array[t]<<endl;
cout<<endl;
}
}
cout<<"please input the number of place you are(0, 12): "<<endl;
int p;
cin>>p;
while(p<0 || p>12)
{
cout<<"please input the valid number(0, 12): ";
cin>>p;
}
cout<<"please input the number of place you want to(0, 12): "<<endl;
int q;
cin>>q;
while(q<0 || q>12)
{
cout<<"please input the valid number(0, 12): ";
cin>>q;
}
if(p != q)
{
int second_array[13];
map.set_distances(p, second_array);
cout<<"The shortest path "<<" from "<<p<<" to "<<q<<"passed by the following places："<<p<<"-";
map.number[q].passed_way.pop();
while(map.number[q].passed_way.front() != q)
{
cout<<map.number[q].passed_way.front()<<"-";
map.number[q].passed_way.pop();
}
cout<<q<<endl;;
cout<<"The total length is："<<second_array[q]<<endl;
cout<<endl;
int x;
cin>>x;
}
else
{
cout<<"you are the place you want to !";
int x;
cin>>x;
}
cout<<endl;
return 0;
}