管理数量方法习题(15)

习题8

1.求v1到其余各点的最短路。

1

v1

2

2

3

3

2

v3

图7-6

2．求v1到其余各点的最短路。

v5

v4 3

v2

7

6

6

图7-7

1．解：

１）给v1标号（０ ｓ）,从v1到v1的距离Ｐ（v1）＝０，v1为起点 标号的点的集合Ｉ＝｛v1｝，没有标号的点的集合J=｛v２ v３ v４ v５ v６｝，弧集 Ａ＝｛vｉ vｊ︱ vｉ ∈ Ｉ vｊ∈ Ｊ｝＝｛（v１ v２） （v１ v３ ）｝ Ｔ１２＝Ｐ（v1）＋ｗ１２＝０＋１＝１ Ｔ１３＝Ｐ（v1）＋ｗ１３＝０＋２＝２

Ｔ１２ Ｔ１３｝＝Ｔ１２ ＝１，给弧（v１ v２）的终点 v２以双标号（１，１）

３）标号的点的集合Ｉ＝｛v1 v２｝，没有标号的点的集合J=｛v３ v４ v５ v６｝，弧集 Ａ＝｛vｉ vｊ︱ vｉ ∈ Ｉ vｊ∈ Ｊ｝＝｛（v１ v３）（v２ v６）（v２ v４）（v２ v３）｝ Ｔ１３＝２ Ｔ２６＝８ Ｔ２４＝３ Ｔ２３＝４

Ｔ１３Ｔ２６ Ｔ２４Ｔ２３ ｝＝２，给弧（v１ v3）的终点 v3以双标号（2，１） 标号的点的集合Ｉ＝｛v1 v２ v３｝，没有标号的点的集合J=｛ v４ v５ v６｝，弧集 Ａ＝｛vｉ vｊ︱ vｉ ∈ Ｉ vｊ∈ Ｊ｝＝｛（v3 v4）（v3 v６）（v２ v４）（v２ v３） （v２ v６）}

Ｔ24 Ｔ26 Ｔ34 Ｔ35 ｝＝Ｔ24 ＝3，给弧（v2 v4）的终点 v４以标号（3，2）. 标号的点的集合Ｉ＝｛v1 v２ v３ v4 ｝，没有标号的点的集合J=｛ v５ v６｝，弧集 Ａ＝｛vｉ vｊ︱ vｉ ∈ Ｉ vｊ∈ Ｊ｝＝｛（v２ v６）（v3 v5）（v4 v６）}

Ｔ26 Ｔ46 Ｔ35 ｝＝Ｔ35 ＝4，给弧（v3 v5）的终点 v5以双标号（4，3）。 标号的点的集合Ｉ＝｛v1 v２ v３ v4 v５｝，没有标号的点的集合J=｛ v６｝，弧集 Ａ＝｛vｉ vｊ︱ vｉ ∈ Ｉ vｊ∈ Ｊ｝＝｛（v２ v６）（v4 v６）（v5 v6）}

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新高中教育管理数量方法习题(15)全文阅读和word下载服务。