数据结构第七章图

第7章图7.1图的定义和术语图(Graph)是一种数据结构，形式定义

Graph=(V,R)

其中：V={x|x∈dataobject}R={VR}VR={<x,y>|p(x,y)∧(x,y∈V)}p(x,y)表示从x到y的一条通路图的抽象数据类型定义：ADTGraph{

数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：

R={VR}VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}

基本操作P：

GreateGraph(&G,V,VR);DestroyGraph(&G);LocateVex(G,u);GetVex(G,v);PutVex(&G,v,Value);FirstAdjVex(G,v);NextAdjVex(G,v,w);InsertVex(&G,v);DeleteVex(&G,v);InsertArc(&G,v,w);DeleteArc(&G,v,w);DFSTraverse(G,v,Visit());BFSTraverse(G,v,Visit());}ADTGraphv2v1v3v4v5v2v1v4v3例如：G1=(v1,{A1})其中：

v1={v1,v2,v3,v4,}A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}例如：G2=(v2,{E2})其中：

v2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3)(v2,v5),(v3,v4),(v3,v5)}设图中顶点数为n，边或弧数为e，则：对于无向图，e的取值范围为0~~n(n-1)/2具有n(n-1)/2条边的无向图称为完全图对于有向图，e的取值范围为0~~n(n-1)具有n(n-1)条边的有向图称为有向完全图和图中边相关的数叫作权（weigth）带权的图称为网顶点的度是和该顶点相关联的边的数目。记作TD(v)以顶点v为头的弧的数目称为v的入度。记作ID(v)以顶点v为尾的弧的数目称为v的出度。记作OD(v)顶点v的度TD(v)=ID(v)+OD(v)邻接点：对于无向图G=(V,{E})，如果边(v,v’)∈E,则称顶点v和v’互为邻接点路径：路径是顶点的序列V={Vi0,Vi1,……Vin}，

满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路径长度：沿路径边的数目或沿路径各边权值之和回路：第一个顶点和最后一个顶点相同的路径简单路径：序列中顶点不重复出现的路径简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路连通：从顶点V到顶点W有一条路径，则说V和W是连通的连通图：无向图中任意两个顶点都是连通的连通分量：无向图中的极大连通子图强连通图：有向图中，如果对每一对Vi,VjV,ViVj,从Vi到

Vj和从Vj到Vi都存在路径，则称G是强连通图强连通分量：有向图中的极大强连通子图有向完全图：具有n(n-1)条边的有向图无向完备图：具有n(n-1)/2条边的无向图权：与图的边或弧相关的数网：带权的图7.2图的存储结构多重链表例G12413V1V2^^V4^V3^例15324G2^V1V2V4^V5^V3实际中不适用数组表示法（邻接矩阵）设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵A[i][j]=1,若(Vi,Vj)E或<Vi,Vj>E0,其它例G1v2v4v1v3例v1v5v3v2v4G2v1v3v2v4v1v3v2v4v5图的数组（邻接矩阵）存储表示#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,djMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM]; AdjMatrixarcs; intvexnum,arcnum;GraphKindkind;}MGraph;特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵中第i行元素之和有向图中，顶点Vi的出度是邻接矩阵中第i行元素之和顶点Vi的入度是邻接矩阵中第i列元素之和易于实现基本操作A[i][j]=Wi,j,若(Vi,Vj)E或<Vi,Vj>E∞,其它网的邻接矩阵可定义为：例v1v4v5v2v375318642v1v3v2v4v5∞57∞35∞∞487∞∞21∞42∞63816∞采用数组（邻接矩阵）表示法，构造图GStatusCreateGraph(MGraph&G){scanf(&G.kind);switch(G.kind){ caseDG:returnCreateDG(G); caseDN:returnCreateDN(G); caseUDG:returnCreateUDG(G); caseUDN:returnCreateUDN(G);default:returnERROR;}}采用数组（邻接矩阵）表示法，构造无向网GStatusCreateUDN(MGraph&G){scanf(&G.vexnum,&G.arcnum,&IncInfo);for(i=0;i<G.vexnum;++i)scanf(&G.vexs[i]);for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){ scanf(&v1,&v2,&w); i=LocateVex(G,v1);j=LocateVex(G,v2); G.arcs[i][j].adj=w; if(IncInfo)Input(*G.arcs[i][j].info); G.arcs[j][i]=G.arcs[i][j]; }returnOK}邻接表表示例G1v2v4v1v3例v1v5v3v2v4G20123v1v3v4v2vexdatafirstarc2130^^^^adjvexnext0123v1v3v4v2vexdatafirstarc1423^^^adjvexnext5v5320^41021^图的邻接表存储表示#defineMAX_VERTEX_NUM20typedefstructArcNode{int adjvex;structArcNode*nextarc;InfoType *info;}ArcNode;typedefstructVnode{VertexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListVertices;int vexnum,arcnum;int kind;}ALGraph;adjvexnextarcinfo表结点datafirstarc头结点特点若无向图中有n个顶点、e条边，则需n个头结点和2e个表结点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1v2v4v1v30123v1v3v4v2vexdatafirstarc30^0^^2^adjvexnext

十字链表------有向图的另一种存储结构tailvexheadvexhlinktlinkdatafirstinfirstout有向图的十字链表存储表示#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;}ArcBox;typedefstructVexNode{VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];intvexnum,arcnum;}OLGraph;例v2v4v1v3v1v2v3v4012302012320323130^^^^^^^^tailvexheadvexhlinktlinkdatafirstinfirstout采用十字链表存储结构，构造有向图StatusCreateDG(OLGraph&G){scanf(&G.vernum,&G.arcnum,&IncInfo);for(i=0;i<G.vexnum;++i){scanf(&G.xlist[i].data);G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;}for(k=0;k<G.arcnum;++k){scanf(&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);p=(ArcBox*)malloc(sizeof(ArcBox));*p={i,j,G.xlist[j].firstin,G.xlist[i].firstout,NULL} //{tailvex,headvex,hlink,tlink,info}G.xlist[j].firstin=G.xlist[i].firstout=p;if(IncInfo)Input(*p->info);}}无向图的邻接多重表存储表示#defineMAX_VERTEX_NUM20typedefemnu{unvisited,visited}VisitIf;typedefstructEBox{VisitIf mark;int ivex,jvex;structEBox*ilink,*jlink;InfoType*info;}Ebox;typedefstructVexBox{VertexType data;EBox*firstedge;}VexBox;typedefstruct{VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;}AMLGraph;markivexilinkjvexjlinkdatafirstedge

邻接多重表-----无向图的另一种存储结构例v1v5v3v2v40123v1v3v4v24v5010323212441^^^^^markivexilinkjvexjlinkdatafirstedge7.3图的遍历图的遍历：从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。

操作的抽象，可以是对结点进行的各种处理可以以输出结点的数据为例来理解在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。

FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构7.3图的遍历不同结构中逻辑关系的对比一、深度优先搜索(DepthFirstSearch)方法：从图的某一顶点V出发，访问此顶点；然后依次从V的未被访问的邻接点出发，深度优先搜索图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。深度优先搜索序列：V1V2V3V1V4V5V6V7V2V8V7V3V4V5V3V6V2V8V1V2V3V4V5V6V7V8v1v2v4v8v5v3v6v7遍历操作中要解决的关键问题：①“从图的某一顶点V出发”，如何选取出发顶点。解决方案：按存储结构排列顺序的第一个。②“依次从V的未被访问的邻接点出发”中“依次”解决方案：按基本操作，先找第一邻接点，再找下一个,循环查找各邻接点。③“未被访问的”邻接点解决方案：设访问标志数组visited[

]

④非连通图解决方案：从任意一个未被访问的结点出发调用算法

算法7.47.5深度优先算法Booleanvisited[MAX];Status(*VisitFunc)(intv);voidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}

voidDFS(GraphG,intv){visited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}问题：判断给定图是否是连通图？多少个连通分量深度遍历：V10123v1v3v4v2vexdatafirstarc2571^^^adjvexnext4v5640^30171^v6v7v8567625243^^^V2V4V8V5V3V6V7V1V2V3V4V5V6V7V8voidDFS(GraphG,intv){visited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}邻接矩阵存储结构voidDFS(MGraphG,intv){visited[v]=TRUE;VisitFunc(v);for(j=0;j<G.vexnum;j++)if(G.arcs[v][j].adj==1&&!visited[j])DFS(G,j);}邻接表存储结构voidDFS(ALGraphG,intv){visited[v]=TRUE;VisitFunc(v);p=G.vertices[v].firstarc;while(p){if(!visited[p->adjvex])DFS(G,p-adjvex);p=p->nextarc;}

时间复杂度：O(n2)

时间复杂度：O(n+e)二、广度优先搜索(BreadthFirstSearch)方法：从图的某一顶点V出发，访问了V之后，依次访问V的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问为止。广度遍历：V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8voidBFSTraverse(GraphG,Status(*visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueue(Q);for(v=0;v<G.vexnum;++v)if(!visited[v]){visited[v]=TRUE;visit(v);EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u); for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;visit(w);EnQueue(Q,w)}//if}//while}//if}

时间复杂度：邻接矩阵存储：O(n2)

邻接表存储：O(n+e)V1V2V3V4V5V6V7V8问题：二叉树按层次遍历问题：迷宫问题7.4图的连通性问题一、无向图的连通分量和生成树对无向非连同图进行深度优先遍历三次调用得到的访问序列为：ALMJBFCDEGKHIABCDEFGHIJKLMALJMBFCDEGKHI生成树：所有顶点均由边连接在一起，但不存在回路的图。深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林。说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树建立非连通图G的深度优先生成森林voidDFSForest(GraphG,CSTree&T){T=NULL;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v]){p=(CSTree)malloc(sizeof(CSNode));*p={GetVex(G,v),NULL,NULL};if(!T)T=p;elseq->nextsibling=p;q=p;DFSTree(G,v,p);}}从第v个顶点出发深度优先遍历图G，建立以T为根的生成树voidDFSTree(GraphG,intv,CSTree&T){visited[v]=TRUE;first=TRUE;for(w=FisrtAdjVex(g,v);w;w=NextAdjVex(G,u,w))if(!visited[w]){p=(CSTree)malloc(sizeof(CSNode));*p={GetVex(G,w),NULL,NULL};if(first){T->lchild=p;first=FALSE;}else{q->nextsibling=p;}q=p;DFSTree(G,w,q);}}二、最小生成树问题提出：要在n个城市间建立通信联络网，顶点表示城市，边上的权值表示城市间建立通信线路所需花费代价，现希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小———最小代价生成树。问题分析：991886261312n个城市间，最多有n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费(各边权值之和)最小。构造一个最小生成树12345性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中uU,vV-U，则必存在一棵包含边(u,v)的最小生成树。普里姆(Prim)算法算法思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树6513566425123456123456Struct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];0v16v11v15∞∞adjvexlowcost0(v1)1(v2)2(v3)3(v4)4(v5)5(v6)0v350v15v36v34U={V1}V-U={V2,V3,V4,V5,V6}U={V1,V3}V-U={V2,V4,V5,V6}0v350v62v360U={V1,V3,V6}V-U={V2,V4,V5}U={V1,V3,V6,V4}V-U={V2,V5}0v3500v360U={V1,V3,V6,V4,V2}V-U={V5}0000v230U={V1,V3,V6,V4,V2,V5}V-U={}0000006513566425123456voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)if(j!=k)closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minimum(closedge);printf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};}}克鲁斯卡尔(Kruskal)算法算法思想：设连通网N=(V,{E})，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边依此类推，直至T中所有顶点都在同一连通分量上为止。1234565135664251234561234567.5有向无环图及其应用有向无环图（DirectedAcyclineGraph）一个无环的有向图,简称DAG图DAG图有向树有向图用有向无环图描述含有公共子式的表达式例((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)*+**+ab*b+cd*+cde+cde*+*e*+*+abcd一、拓扑排序拓扑排序（TopologicalSort）:由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。

若集合X上的关系R是自反的，反对称的和传递的，则称R是集合X上的偏序关系。

设R是集合X上的偏序关系，如果对每个小x,yX

必有xRy或yRx，则称R是集合X上的全序关系。V1V2V3V4学生选修课程问题顶点——表示课程有向弧——表示先决条件，若课程i是课程j的先决条件，则图中有弧<i,j>学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序课程代号课程名称先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8一个AOV网的拓扑序列不是唯一的顶点表示活动，弧表示优先关系的有向图称为顶点表示活动的网（ActivityOnVertexNetwork）简称AOV网C9C1C3C2C4C5C7C6C8C12C11C10拓扑排序的方法1）在有向图中选一个没有前驱的顶点且输出之2）从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止C9C1C3C2C4C5C7C6C8C12C11C10拓扑排序算法：1）扫描顶点表，求各顶点入度indegree[0..vernum-1]2）初始化栈，入度为0的顶点入栈，计数count=0;3）当栈不空时重复

1、取栈顶顶点，并输出，计数count++;2、取该顶点的所有邻接点将其入度减1，若减1后入度为0，则该顶点入栈。4）当栈空时，若输出的顶点数count小于图的顶点数，则图有回路，否则正常StatusTopologicalSort(ALGraphG){FindInDegree(G,indegree);//求各顶点的入度indegree[0..vernum-1]InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);count=0;while(!StackEmpty(S)){Pop(S,i);printf(i,G.vertices[i].data);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k]))Push(S,k);}}if(count<G.vexnum)returnERROR;elsereturnOK;}时间复杂度：O(n+e)二、关键路径问题提出：把工程计划表示为有向图，用顶点表示事件，弧表示活动；权表示活动持续的时间。例设一个工程有11项活动，9个事件事件V1——表示整个工程开始事件V9——表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE网(ActivityOnEdge)——边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。路径长度——路径上各活动持续时间之和关键路径——路径长度最长的路径Ve(j)——表示事件Vj的最早发生时间Vl(j)——表示事件Vj的最迟发生时间e(i)——表示活动ai的最早开始时间l(i)——表示活动ai的最迟开始时间l(i)-e(i)——表示完成活动ai的时间余量关键活动——关键路径上的活动。987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771416181814167108660511求ve(j)和vl(j)需分两步进行：1）从ve(0)=0开始向前递推：ve(j)=Max{ve(i)+dut(<i,j>)}

i

<i,j>Tj=1,2,…n-1其中：T为所有以j为头的弧的集合ij2）从vl(n-1)=ve(n-1)起向后递推：vl(i)=Min{vl(j)-dut(<i,j>)}

j

<i,j>Sj=1,2,…n-1其中：S为所有以i为尾的弧的集合ij算法实现1)从源点V1出发，令ve[0]=0,按拓扑序列求各顶点的最早开始时间ve[i]2）从汇点Vn出发，令vl[n-1]=ve[n-1],按逆拓扑序列求其余各顶点的最迟发生时间vl[i]3）根据各顶点的Ve和Vl值，计算每条弧的最早开始时间e[i]和最迟开始时间l[i],找出e[i]=l[i]的关键活动StatusTopologicalOrder(ALGraphG,Stack&T){FindInDegree(G,indegree);//建立0入度顶点栈SInitStack(T);count=0;ve[0..G.vexnum–1]=0;while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;if(--indegree[k]==0)Push(S,k);if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}}if(count<G.vexnum)returnERROR;elsereturnOK;}jkStatusCriticalPath(ALGraphG){if(!TopologicalOrder(G,T))returnERROR;vl[0..G.vexnum–1]=ve[G.vexnum–1];while(!StackEmpty(T))for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);if(vl[k]–dut<vl[j])vl[j]=vl[k]–dut;}for(j=0;j<G.vexnum;++j)for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);ee=ve[j];el=vl[k]–dut;tag=(ee==el)?’*’:‘’;printf(j,k,dut,ee,el,tag);}}jk时间复杂度：O(n+e)7.6最短路径问题提出图中：顶点：表示城市边：表示城市间的交通联系权：表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径ABC832用带权的有向图表示一个交通运输网一、从某个源点到其余各顶点的最短路径迪杰斯特拉(Dijkstra)算法基本思想把图中所有顶点分成两组，第一组包含已确定最短路径的顶点，第二组包含尚未确定最短路径的顶点，按最短路径递增的顺序，逐个把第二组的顶点加到第一组中去，直至从V0出发可以达到的所有顶点都包含到第一组中。v0100v4v5v3v2v13060101020505第一组第二组v0v1,v2,v3,v4,v5v1=∞

v2=10v3=∞v4=30v5=100v2=10

v3=60(v2)v4=30v5=90(v4)v3=50(v4)

v5=60(v4v3)v5=60(v4v3)

v3=50(v4)

求最短路径步骤初始时令S={V0},T={其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，为<V0,Vi>弧上的权值若不存在<V0,Vi>，为∞从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止voidDIJ(MgraphG,intv0,PathMatrix&P,ShortPathTable&D){for(v=0;v<G.vexnum;++v){final[v]=FALSE;D[v]=G.arcs[v0][v];for(w=0;w<G.vexnum;++w)P[v][w]=FALSE;if(D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}D[v0]=0;final[v0]=TRUE;for(i=1;i<G.vexnum;++i){min=INFINITY;for(w=0;w<G.vexnum;++w)if(!final[w])if(D[w]<min){v=w;min=D[w];}final[v]=TRUE;for(w=0;w<G.vexnum;++w)if(!final[w]&&(min+G.arcs[v][w]<D[w])){D[w]=min+G.arcs[v][w];P[w]=P[v];P[w][w]=TRUE;}}}时间复杂度：O(n2)二、每一对顶点之间的最短路径方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次，

其时间复杂度为：O(n³)方法二：弗洛伊德(Floyd)算法算法基本思想：递推地产生一个矩阵序列：D(-1