实验六：编程实现Dijkstra 算法求最短路问题.
1.需求分析：
首先让用户输入一个带权的有向图，输入时可通过一对一对输入存在弧的两个弧头与弧尾顶点以及弧上的权值从而输入整个有向图。
用户输入一对对弧后，我们可以采用数组的形式来进行存储每个顶点之间的权值，最后由用户输入该有向图的源点（即每个最短路径的起点），要求源点必须为刚才输入的各顶点中的某一个，如果用户输入错误，程序要给出错误信息提示并退出程序。
然后，我们可以设计一个Graph这样的类，将对关系的各种操作放入其中，然后我们在主函数中调运这个类就可以实现最短路问题的求解了。
2.概要设计：
①.构造一个新的类Graph:
class Graph
{
private: int arcs[MAX][MAX],Path[MAX][MAX],D[MAX];
int arcnum,vexnum,weight,v0;
Type a,b,vexs[MAX];
public:
void Creat_Graph();
void Show_ShortestPath();
void ShortestPath_DIJ();
};
②.结构化调用类中方法的主函数：
int main()
{
Graph <char> G;
G.Creat_Graph();
G.ShortestPath_DIJ();
G.Show_ShortestPath();
return 0;
}
3.代码实现：
#include<iostream>
#define MAX 100
#define INFINITY INT_MAX
enum BOOL{FALSE,TRUE};
using namespace std;
template <typename Type>
class Graph
{
private: int arcs[MAX][MAX],Path[MAX][MAX],D[MAX];
int arcnum,vexnum,weight,v0;
Type a,b,vexs[MAX];
public:
void Creat_Graph();
void Show_ShortestPath();
void ShortestPath_DIJ();
};
template <typename Type>
void Graph<Type>::Creat_Graph()
{
int i,j,x,y;
cout<<"请输入你要处理的有向图中包含弧的个数：";
cin>>arcnum;
vexnum=0;
for(i=1;i<=MAX;i++)
for(j=1;j<=MAX;j++)
arcs[i][j]=INT_MAX;
for(i=1;i<=arcnum;i++)
{
cout<<"请依次输入第"<<i<<"条弧的弧头与弧尾的顶点以及该弧上所附带的权值："<<endl;
cin>>a>>b>>weight;
x=0; y=0;
for(j=1;j<=vexnum;j++)
{
if(vexs[j]==a)
{
x=j; continue;
}
else if(vexs[j]==b)
{
y=j; continue;
}
}
if(x==0)
{
vexs[++vexnum]=a; x=vexnum;
}
if(y==0)
{
vexs[++vexnum]=b; y=vexnum;
}
arcs[x][y]=weight;
}
cout<<"请输入该有向图的源点(即各最短路径的起始顶点)：";
cin>>a;
for(i=1;i<=vexnum;i++)
{
if(vexs[i]==a)
{
v0=i; break;
}
}
}
template <typename Type>
void Graph<Type>:: Show_ShortestPath()
{
int i,j,k;
for(i=1;i<=vexnum;i++)
{
if(i==v0) continue;
if(D[i]!=INT_MAX)
{
cout<<"从源点"<<vexs[v0]<<"到"<<vexs[i]<<"的最短路径为："<<endl;
for(k=1;k<=Path[i][0];k++)
{
if(k!=1)
cout<<"-->";
for(j=1;j<=vexnum;j++)
if(Path[i][j]==k)
cout<<vexs[j];
}
cout<<" "<<"其最短的路径长度为："<<D[i]<<endl;
}
else
{
cout<<"无法从源点"<<vexs[v0]<<"到达顶点"<<vexs[i]<<"."<<endl;
}
}
cout<<endl;
}
template <typename Type>
void Graph<Type>::ShortestPath_DIJ()
{
int v,w,final[MAX],min,i,j;
for(v=1;v<=vexnum;v++)
{
final[v]=FALSE; D[v]=arcs[v0][v]; Path[v][0]=0;
for(w=0;w<=vexnum;w++)
Path[v][w]=FALSE;
if(D[v]<INT_MAX)
{ Path[v][v0]=++Path[v][0]; Path[v][v]=++Path[v][0]; }
}
D[v0]=0; final[v0]=TRUE;
for(i=1;i<=vexnum;i++)
{
if(i==v0) continue;
min=INT_MAX;
for(w=1;w<=vexnum;w++)
if(!final[w])
if(D[w]<min) { v=w; min=D[w]; }
final[v]=TRUE;
for(w=1;w<=vexnum;w++)
if(!final[w]&&(min+arcs[v][w]<D[w])&&min<INT_MAX&&arcs[v][w]<INT_MAX)
{
D[w]=min+arcs[v][w];
for(j=0;j<=vexnum;j++)
Path[w][j]=Path[v][j];
Path[w][w]=++Path[w][0];
}
}
}
int main()
{
Graph <char> G;
G.Creat_Graph();
G.ShortestPath_DIJ();
G.Show_ShortestPath();
return 0;
}
4.调试分析：
❶起先在主函数中调用类Graph时将类型参数T赋值为int从而导致用户输入的关系集合R中的元素必须为整数。
经分析后将T赋值为char，当用户输入的R的元素为int时，我们可以将其转化为char在进行后续操作，从而实现对用户输入的关系R中元素的无限制。
❷在类Graph的模板外定义成员函 G.Creat_Graph()﹑G.ShortestPath_DIJ()﹑
G.ShortestPath_DIJ()时，由于成员函数中有类型参数存在，则需要在函数外进行模块声明，并且在函数名前缀上“类名<类型参数>∷”。
5.运行结果：
下图为有向图G的带权邻接矩阵，运用Dijkstra算法计算从A到其余各顶点的最短路径以及其长度。
A B C D E F
┏┓分析可知：
A┃∞∞ 10 ∞ 30 100┃从A到C的最短路径为：A→C，其长度为10；
B┃∞∞ 5 ∞∞∞┃从A到E的最短路径为：A->E,其长度为30；
C┃∞∞∞ 50 ∞∞┃从A到D的最短路径为：A→E->D，其长度为50;
D┃∞∞∞∞∞ 10┃从A到F的最短路径为：A→E->D->F，其长度为60; E┃∞∞∞ 20 ∞ 60┃而从A无法到达B。
F┃∞∞∞∞∞∞┃易知：运行结果完全正确。
┗┛。