7_2图(拓扑排序、关键路径、最短路径)

《7_2图(拓扑排序、关键路径、最短路径)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图(拓扑排序、关键路径、最短路径)四、有向无环图有向无环图概念四、有向无环图拓扑排序拓扑排序的概念四、有向无环图拓扑排序拓扑排序算法E1：计算各顶点的入度；E2：将入度为0的顶点入栈；E3：循环直到栈空：E31：从栈中弹出一个顶点，输出到拓扑序中；E32：将该顶点的所有邻接点的入度减1，若某个邻接点的入度减为0，则将该邻接点入栈；入度indegree[]栈（顶-底）输出v1v2v3v4v5v6022103v5,v1021102v1v5010002v4,v3v5,v1000001v2,v3v5,v1,v4000001v3v5,v1,v4,v2000000v6

2、v5,v1,v4,v2,v3v5,v1,v4,v2,v3,v6四、有向无环图关键路径关键路径的概念及意义四、有向无环图关键路径关键路径的计算E1：依拓扑序计算各顶点的最早发生时间ve；E2：依逆拓扑序计算各顶点的最迟发生时间vl；E3：计算每条弧的最早开始时间e和最迟开始时间l，若e等于l，则输出该弧（关键弧）；四、有向无环图关键路径关键路径的计算最早发生时间ve的计算初值的选择ve[k]=max{ve[i]+w[i][k]

3、∈E}四、有向无环图关键路径关键路径的计算最迟发生时间vl的计算初值的选择vl[i]=min{vl[j]-w[i][j]

4、<

5、vi,vj>∈E}四、有向无环图关键路径关键路径的计算弧的最早开始时间和e和最迟开始时间l的计算eij=ve[i]lij=vl[j]-w[i][j]0/0/0/0/0/0/0/0/0/0/0/0/5/0/24/41/15/3/21/18/28/41/50/62/5/620/6224/6241/6215/623/6221/6218/6228/6241/6250/6262/625/50/024/2441/4115/153/921/2718/1928/2941/4750/5062/625/50/024/2441/4115/153/921/2718/1928/2941/

6、4750/5062/620/00/65/125/53/113/915/1615/4324/2418/1921/2728/4228/2915/1541/4141/4350/5033/470/05/524/2415/1541/4150/50五、最短路径单源起点的最短路径问题五、最短路径Dijstra算法算法思想Idea1设，M={P0,i,P0,i是v0到vi的最短路径

7、i=1…n-1}，设，已知权值W0,k=min({W0,i

8、∈E})，即，是v0到其他各顶点的直达弧中最短的，则，P0,k=(v0,vk)∈M，(v0,vk)是Ｍ中最短的

9、一条路径！五、最短路径Dijstra算法算法思想Idea2设，M={P0,i,P0,i是v0到vi的最短路径

10、i=1…n-1}，设，P0,k=(v0,vk)是M中的最短路径，P0,i是Ｍ中的次短路径，则，P0,i=(v0,vi)或Ｐ0,i=(v0,vk,vi)P0,i是次短路径=>W0,i

11、i=1…n-1}，设，已知M的一个子集U，且U中的路径均短于M-U中的路径，设，P0,i是M-U中的

12、最短的路径，则：P0,i=(v0,vi)或P0,i=P0,k+{vi}，其中P0,k∈U五、最短路径Dijstra算法设辅助向量u[0…n-1]、shortest[0…n-1]和path[0…n-1]；u[i]为１表示从v0到vi的最短路径已经求出，为０表示尚未求出；shortest[i]记录目前已知的从v0到vi的较短路径的长度；path[i]记录目前已知的从v0到vi的较短路径；初始时，设置从v0到vi的直达弧为目前已知的较短路径；五、最短路径Dijstra算法E1：初始化辅助向量u、shortest、path；E2：循环n-1次：E21：从M-U中选择最小

13、的shortest[k]；E22：将vk并入Ｕ中;E23：对M-U中的各顶点vi的已知较短路径进行修正：若P0,k+{i}的长度短于目前已知的P0,i的长度，则用P0,k+{i}取代原P0,i；CODING0124531741045201141361291421已知弧上带权值的有向图，计算从V0到其他各顶点的最短路径。012453174104520114136129142121/05/0∞/012/017/0已知弧上带权值的有向图，计算从V0到其他各顶点的最短路径。12345shortest1721125∞path00000已求出最短路径的顶点集合为：001

14、245317410452