文档介绍：狄克斯拉算法的上机报告计算092 杜青 3090811050问题描述:对于有向带权图中从一个确定的结点(称为源点)到其余各结点的最短路径问题。基木要求:能够会使用利用图的结构编写函数,实现找到最短路径。能够找到从某一结点到其它结点嚴短路径的前一个结点,记录整个最短路径路径经过的务个结点。测试数据:a[]={A,'B',C,D,E,'F};row[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2丄15},{2,5,7},{4,3,4},{5,3,10},{5,4,18}};算法思想:设置两个结点的集合S和T,集合S屮只存放己找到最短路径的结点,集合T屮存放当前还未找到最短路径的结点。初始状态时,集合S屮只包含源点,设为v0,然示不断地从集合T屮选择到源点v0的路径长度最短的结点u放在集合S中,集合S毎加入一个新的结点u都要修改从源点v0到集合T屮剩余结点的当前的最短路径长度值,集合T屮备结点的新的当前最短路径长度值,为原来的最短路径长度值从源点过结点u到达该结点的路径长度屮的较小者。此过程不断重复,直到集合T的全部结点加入到集合S屮为止。模块划分:(&g,a,n,row,e)^J功能把输入的数据转化为图的结构。2,Dijkstra(g,0,distance,path)的功能的功能是把求故短路径的核心算法。函数设计有四个参数,其屮两个为输入函数,分别为distanced和path]]。Distanced)IJ来存放得到的源点v0到其余备结点的最短路径数值,path[]用来存放得到的源点vO到其余备结点的最短路径上到达目标结点的前一个结点下标。数据结构:使用主要的数据结构为顺序表的结构。邻接矩阵存储结构下图的结点信息存储在一顺序表屮,图的边信息存储在一个二维数组屮。源程序:typedefstruct{DataTypelist[MaxSize];intsize;JSeqList;voidListInitiate(SeqList*L)L->size=O;gth(SeqListL){;)intListInsert(SeqList*L,inti,DataTypex){intj;if(L->size>=MaxSize){printf("顺序表已满无法插入!\rT);return0;}elseif(i<0lli>L->size){printf(”参数i不合法!\n”);return0;}else{for(j=L->size;j>i;j—)L->list[i]=x;L->size++;return1;}}intListGet(SeqListL,inti,DataType*x){if(i<()lli>-l){printfC*参数i不合法!\n”);return0;}else{*x=[i];return1;}}intListDelete(SeqList*L,inti,DataType*x){intj;if(L->size<=0)printf(“顺序表已空无数据元素可删!\n“);return0;}elseif(i<Olli>L->size-l){printfC1参数i不合法“);return0;}else{*x=L->list[i];for(j=i+1;j<=L->size