11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55) ;现引

参考答案:

C解析：本题是一个典型的图论算法的应用问题。既可以看作赋权简单连通无向图的单源问题进行求解，也可以用两结点间最短距离算法进行求解。 采用单源问题的迪克斯特拉(E．W Dijkstra)算法求解。 将题图中未标记的结点进行标记，得到下图： 令S={s}，T={a，b，c，d，e，f，S，h，i，t}， D(s)=0，D(a)=25，D(b)=21，D(c)=+∞，D(d)=+∞，D(e)=+∞，D(f)=+∞， D(g)=+∞，D(h)=+∞，D(i)=+∞，D(t)=+∞。因为D(b)=21是T中最小的D