Tasks.Data_Structure

数据结构 第四次实验课作业

题目

第八章实验题7

采用狄克斯特拉算法求带权有向图的最短路径

目的

领会狄克斯特拉算法求带权有向图中单源最短路径的过程和相关算法设计。

内容

编写一个程序exp8-7.cpp，实现求带权有向图中单源最短路径的狄克斯特拉算法。并输出如图 8.54所示的带权有向图G中从顶点0到达其他个顶点的最短路径长度和最短路径。 实验程序exp8-7.cpp的结构如图所示，图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成，即指出该虚线框中的函数存放在哪个文件中。

exp8-7.cpp 的结构图
          +-----------------+
          | exp8-7.cpp      |
          +-----------------+
 /------- | - main()        | ->--\
 |        | - Dijkstra()    | <---+
 |        | - Dispath()     | <---/
 |        +-----------------+
 |
 |    +-----------------+
 |    | graph.cpp       |
 |    +-----------------+
 +--> | + CreateMat()   |
 \--> | + DisMat()      |
      +-----------------+

图 8.54

图可视化编辑器：
https://csacademy.com/app/graph_editor/
渲染模式：有向图模式
图结点数：6
图数据：
0
1
2
3
4
5
0 1 5
0 3 7
1 2 4
2 0 8
2 5 9
3 2 5
3 5 6
4 3 5
5 4 1
5 0 3

第八章实验题9

求AOE网中的所有关键活动

目的

领会拓扑排序的AOE网中关键路径的求解过程及算法设计。

内容

编写一个程序exp8-9.cpp，求《教程》中图 8.45所示的AOE网的所有关键内容。 实验程序exp8-9.cpp的结构如图所示，图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成，即指出该虚线框中的函数存放在哪个文件中。

exp8-9.cpp 的结构图
          +-----------------+
          | exp8-7.cpp      |
          +-----------------+
 /------- | - main()        | ->--\
 |        | - DisKeyno()    | <---+
 |        | - KeyPath()     | <---+
 |        | - TopSort()     | <---/
 |        +-----------------+
 |
 |    +-----------------+
 |    | graph.cpp       |
 |    +-----------------+
 +--> | + CreateAdj()   |
 +--> | + DispAdj()     |
 \--> | + DestroyAdj()  |
      +-----------------+

图 8.45

图可视化编辑器：
https://csacademy.com/app/graph_editor/
渲染模式：有向图模式
图结点数：9
图数据：
A
B
C
D
E
F
G
H
I
A B a_1=6
A C a_2=4
A D a_3=5
B E a_4=1
C E a_5=1
D H a_6=2
E F a_7=9
E G a_8=7
H I a_9=4
F I a_10=2
G I a_11=4
便于处理的版本：
A
B
C
D
E
F
G
H
I
A B 6
A C 4
A D 5
B E 1
C E 1
D H 2
E F 9
E G 7
H I 4
F I 2
G I 4

提交

  1. 将作业打包为压缩文件，如 zip 格式。
  2. 压缩文件命名为你的学号， 如 2018302114514.zip 。
  3. 将压缩文件以附件形式发送到邮箱 DS_Exp4 # superexercisebook.com
  4. 如果一切顺利，你将会收到一个投递成功回执。