姓名：张进 学号：03091256 班级：030913班实验六：编程实现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 G;G.Creat_Graph();G.ShortestPath_DIJ();G.Show_ShortestPath();return 0;}3. 代码实现：#include #define MAX 100#define INFINITY INT_MAXenum BOOL{FALSE,TRUE};using namespace std;template 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 void Graph::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<<"请依次输入第"<>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 void Graph:: Show_ShortestPath(){int i,j,k;for(i=1;i<=vexnum;i++){if(i==v0) continue;if(D[i]!=INT_MAX){cout<<"从源点”<";for (j=1;j<=vexnum;j++)if (Path[i][j]==k)cout<void Graph::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] 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的带权邻接矩阵，运用Dijkstr算法计算从A到其余各顶点的最短路径以及其长度ABCDEFrT分析可知：A|8810830100|从A到C的最短路径为：A3C，其长度为10；B |885888|从入到£的最短路径为：A->E,其长度为30；C|8885088|从入到的最短路径为：A”>D，其长度为50;D|8888810 |从A到F的最短路径为：A3E->D->F，其长度为 60;E |88820860 |而从A无法到达BF |888888|易知：运行结果完全正确。