资源描述：
《迪克斯特拉算法报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、姓名：杨网学号：3090811022班级：计算091迪克斯特拉算法报告问题描述：以图所示的有向带权图为例设计测试上述Dijkstra函数的程序。基本要求：（1）初始状态时若从源点v0到某下标为i的结点有边，则distance[i]为该边的权值，且令path[i]为源点v0;若从源点v0到下标为i的结点无边，则distance[i]为最大权值MaxWeight，且令distance[i]为-1。（2）函数设计成一个循环迭代过程。（3）数组path中存放了从源点v0到其他各个节点的最短路径的前一个结点的下标。测试数据：chara[]={‘A’,’B’,’C’,’D’,’E’,’F’};r
2、cw[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2,1,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到底该节点的路径长度中的较小者。此过程不断
3、重复，直到集合T中的接点全部加入集合S中为止。模块划分：(1)voidCreateGraph(AdjMGraph*G,DataTypeV[],intn,RowColWeightE[],inte);在图G中插入n个结点信息V和e条边信息E(2)voidDijkstra(AdjMGraphG,intv0,intdistance[],intpath[]);求最短路径。(3)voidmain(void)，主函数。调用函数Initiate()和函数Dijkstra()数据结构：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;typede
4、fstruct{introw;intcol;intweight;}RowColWeight;typedefstruct{SeqListVertices;intedge[MaxVertices][MaxVertices];intnumOfEdges;}AdjMGraph;源程序：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;//初始化ListInitiate(L)voidListInitiate(SeqList*L)//初始化顺序表{L->size=0;//定义初始元素个数}//求当前数据元素个数ListLength(L)in
5、tListLength(SeqListL)//返回顺序表L的当前数据元素个数{returnL.size;}//插入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex)//在顺序表L的第i个位置前插入数据元素值X//插入成功返回1,失败返回0{intj;if(L->size>=MaxSize){printf("顺序表已满无法插入！");return0;}elseif(i<0
6、
7、i>L->size){printf("参数i不合法！");return0;}else{//未插入做准备for(j=L->size;j>i
8、;j--)L->list[j]=L->list[j-1];L->list[i]=x;//插入xL->size++;return1;}}//删除数据元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x)//删除顺序表{intj;if(L->size<=0){printf("顺序表已空无数据元素可删！");return0;}elseif(i<0
9、
10、i>L->size-1){printf("参数i不合法!");return0;}else{*x=L->list[i];for(j=i+1;j<=L->size-1;j++)
11、L->list[j-1]=L->list[j];L->size--;return1;}}//取数据元素LiseGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0
12、
13、i>L.size-1){printf("参数i不合法！");return0;}else{*x=L.list[i];return1;}}voidDijkstra(AdjMGraphG,intv0,intdistance[],intpath
