给定简单带权有向图,如图 16.20 所示,求结点 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到其他各结点的最短链.[br][/br][img=348x212]178c6311026209e.png[/img]

2022-06-16

给定简单带权有向图,如图 16.20 所示,求结点 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到其他各结点的最短链.[br][/br][img=348x212]178c6311026209e.png[/img]

答案：

解      用Dijkstra算法,将计算结果列表如下:[br][/br][img=925x349]178c6318c219f0f.png[/img][br][/br]        由上表可知,[tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]SP0CzBMUhsl/VedUDlerpQ==[/tex] 的最短链是 1 ;[tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]Gulw75DLpb9Jxz3bC3CYZw==[/tex], 中间经过结点 [tex=0.857x1.0]SP0CzBMUhsl/VedUDlerpQ==[/tex], 其最短链是 2 ;[tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]ZDCVElMiWIdShZcg4z/PtQ==[/tex], 中间经 过结点 [tex=0.857x1.0]SP0CzBMUhsl/VedUDlerpQ==[/tex], [tex=0.857x1.0]Gulw75DLpb9Jxz3bC3CYZw==[/tex] 和 [tex=0.857x1.0]AEEyhu9XXFB5VuTSv4Qf/A==[/tex], 其最短链是[tex=0.857x1.0]SP0CzBMUhsl/VedUDlerpQ==[/tex] ; [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]z1WgSpi7t4Cme8y5zX37vg==[/tex], 中间经过结点 [tex=0.857x1.0]SP0CzBMUhsl/VedUDlerpQ==[/tex], [tex=0.857x1.0]Gulw75DLpb9Jxz3bC3CYZw==[/tex], [tex=0.857x1.0]AEEyhu9XXFB5VuTSv4Qf/A==[/tex] 和 [tex=0.857x1.0]ZDCVElMiWIdShZcg4z/PtQ==[/tex], 其最短链是 16 ; [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex]到[tex=0.857x1.0]ktM2i0v57Y7aEf12pAh0MA==[/tex], 中间经过结点[tex=0.857x1.0]SP0CzBMUhsl/VedUDlerpQ==[/tex], [tex=0.857x1.0]Gulw75DLpb9Jxz3bC3CYZw==[/tex] 和 [tex=0.857x1.0]AEEyhu9XXFB5VuTSv4Qf/A==[/tex], 其最短链是 8 .

举一反三

内容

0
给定图 [tex=6.286x1.214]XufOd2+4/JyAOC1sN9Ukrg==[/tex],其中 [tex=8.0x1.357]4+BcNPi+ZQNigplU25eQlzDSi+8L0nGzSkpQbkU+fUsUF+Ax0hNV8hecC9mG4r4q[/tex], 定义 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的距离矩阵 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 是:[br][/br] [tex=10.786x1.357]3ttqLi1hQqGLj4j9wMryjyvJ1pvljkZWxnT6sEGDTgFtiB/DZJT9rPBBz2lX4RNtofTNvH2iK9l6IOVjXr6FoQ==[/tex][br][/br]对图 16.23中的有向图,试求[br][/br] [img=236x206]178c64a8f0d9412.png[/img][br][/br]试用邻接矩阵 [tex=0.786x1.0]b4HkKtHXeHofHX/gJc8Agg==[/tex] 求出距离矩阵[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex].
1
设有有向图[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]如图6.7所示，试求：（1）每个结点的引入次数与引出次数；（2）它的邻接矩阵[tex=1.571x1.214]rzf0jr3YGqLmoRnJWdiEDA==[/tex]；（3）[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]是强连通、弱连通还是单向连通？（4）求从[tex=0.571x0.786]HXNXn3AXpwdIpZt8+6oCEw==[/tex]到[tex=0.5x0.786]hycNLgozeED/VkKdun7zdA==[/tex]长度小于或等于3的通路数目.[img=337x313]1785f7fbc4ea378.png[/img]
2
已知某离散系统结构图如图 4 所示,采样周期[tex=2.357x1.0]H8LmHwCpGqYY5kuaC76AkA==[/tex]。[br][/br][img=498x187]17a7c5f86286602.png[/img][br][/br]当[tex=3.714x1.357]guKXqQTTT8k2fn+iVs/D7g==[/tex]时,求闭环系统稳定的[tex=0.857x1.0]FfIhW8W8Jb8XV2jfmtoNZA==[/tex]值范围;
3
有向图 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 如图 14.23 所示.(1) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中 [tex=0.857x1.0]z1WgSpi7t4Cme8y5zX37vg==[/tex] 到 [tex=0.857x1.0]ZDCVElMiWIdShZcg4z/PtQ==[/tex] 长度为 1,2,3,4的通路各为几条?(2) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 长度为 1,2,3,4 的回路各为几条?(3) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中长度为 4 的通路共有多少条?其中有多少条是回路?(4) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 是哪类连通图?
4
图[tex=0.5x1.0]HNefUrdF8bed/Hc2JSQNOQ==[/tex]所示桁架，[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]结点有水平荷载作用，求指定杆[tex=1.929x1.286]+A91pi2VXLtyYrVQoi0TLA==[/tex]的轴力。[img=195x172]179ca9c058fa331.png[/img]