综合题
已知加权有向图 G 的邻接矩阵如下：
问答题
画出该有向图 G。
【正确答案】
【答案解析】
问答题
试利用 Dijkstra 算法求 G 中从顶点 a 到其他各顶点间的最短路径， 并给出求解过程。
【正确答案】
表1 Dijkstra 算法求最短路径
| Dist/终点 | b | c | d | e | f | g | S |
| k ＝ 1 | 15 （ a,b ） |
2 （ a,c ） |
12 （ a,d ） |
{a,c} | |||
| k ＝ 2 | 15 （ a,b ） |
12 （ a,d ） |
10 （ a,c,e ） |
6 （ a,c,f ） |
{a,c,f} | ||
| k ＝ 3 | 15 （ a,b ） |
11 （ a,c,f,d ） |
10 （ a,c,e ） |
16 （ a,c,f,g ） |
{a,c,f,e} | ||
| k ＝ 4 | 15 （ a,b ） |
11 （ a,c,f,d ） |
16 （ a,c,f,g ） |
{a,c,f,e,d} | |||
| k ＝ 5 | 15 （ a,b ） |
14 （ a,c,f,d,g ） |
{a,c,f,e,d,g} | ||||
| k ＝ 6 | 15 （ a,b ） |
{a,c,f,e,d,g,b} |
最短路径为：（a，c，f，e，d，g，b）
【答案解析】