7.19.最短路径问题

当你在网上冲浪，发送电子邮件，或从校园的另一个地方登录实验室计算机时，大量的工作正在幕后进行，以获取你计算机上的信息传输到另一台计算机。 深入研究信息如何通过互联网从一台计算机流向另一台计算机是计算机网络中的一个主要课题。 然而，我们将讨论互联网如何工作足以理解另一个非常重要的图算法。

Figure 1

Figure 1 展示了 Internet 上的通信如何工作的高层概述。当使用浏览器从服务器请求网页时，请求必须通过局域网传输，并通过路由器传输到 Internet上。 该请求通过因特网传播，并最终到达服务器所在的局域网路由器。 请求的网页然后通过相同的路由器回到您的浏览器。 在 Figure 1中标记为 “因特网” 的云是附加的路由器。所有这些路由器一起工作，让信息从一个地方到另一个地方。 可以看到有许多路由器，如果你的计算机支持 traceroute 命令。下面的文本显示 traceroute 命令的输出，说明在 Luther College 的Web服务器和明尼苏达大学的邮件服务器之间有13个路由器

1  192.203.196.1
2  hilda.luther.edu (216.159.75.1)
3  ICN-Luther-Ether.icn.state.ia.us (207.165.237.137)
4  ICN-ISP-1.icn.state.ia.us (209.56.255.1)
5  p3-0.hsa1.chi1.bbnplanet.net (4.24.202.13)
6  ae-1-54.bbr2.Chicago1.Level3.net (4.68.101.97)
7  so-3-0-0.mpls2.Minneapolis1.Level3.net (64.159.4.214)
8  ge-3-0.hsa2.Minneapolis1.Level3.net (4.68.112.18)
9  p1-0.minnesota.bbnplanet.net (4.24.226.74)
10  TelecomB-BR-01-V4002.ggnet.umn.edu (192.42.152.37)
11  TelecomB-BN-01-Vlan-3000.ggnet.umn.edu (128.101.58.1)
12  TelecomB-CN-01-Vlan-710.ggnet.umn.edu (128.101.80.158)
13  baldrick.cs.umn.edu (128.101.80.129)(N!)  88.631 ms (N!)
Routers from One Host to the Next over the Internet

互联网上的每个路由器都连接到一个或多个路由器。因此，如果在一天的不同时间运行 traceroute 命令，你很可能会看到你的信息在不同的时间流经不同的路由器。这是因为存在与一对路由器之间的每个连接相关联的成本，这取决于业务量，一天中的时间以及许多其他因素。到这个时候，你不会惊讶，我们可以将路由器的网络表示为带有加权边的图形。

Figure 2

Figure 2 展示了表示互联网中的路由器的互连的加权图的一个小例子。我们要解决的问题是找到具有最小总权重的路径，沿着该路径路由传送任何给定的消息。这个问题听起来很熟悉，因为它类似于我们使用广度优先搜索解决的问题，我们这里关心的是路径的总权重，而不是路径中的跳数。应当注意，如果所有权重相等，则问题是相同的。