ShortestPathProblems.ptx

<section xml:id="graphs_shortest-path-problems">
        <title>Shortest Path Problems</title>
        <p>When you surf the web, send an email, or log in to a laboratory computer
            from another location on campus a lot of work is going on behind the
            scenes to get the information on your computer transferred to another
            computer. The in-depth study of how information flows from one computer
            to another over the Internet is the primary topic for a class in
            computer networking. However, we will talk about how the Internet works
            just enough to understand another very important graph algorithm.</p>
        
        <figure align="center" xml:id="fig-inet">
            <caption>Overview of Connectivity in the Internet.</caption>
                <image source="Graphs/Internet.png" width="80%">
                <description><p>This image represents a simplified network diagram, showing an overview of connectivity in the internet. Two routers, labeled as Router A and Router B, serve as the central connection points. Router A is connected to a cloud labeled "Internet," which symbolizes the global network. On the right side of Router A, there are connections leading to a desktop computer and a laptop, representing end-user devices. On the left side of Router B, connected to the same internet cloud, are two server icons, indicating server machines. The diagram visually explains how different types of hardware devices interface with the internet through routers, depicting a basic structure of network connectivity.</p></description>
                </image>
            </figure>
        <p><xref ref="fig-inet"/> shows you a high-level overview of how communication
            on the Internet works. When you use your browser to request a web page
            from a server, the request must travel over your local area network and
            out onto the Internet through a router. The request travels over the
            Internet and eventually arrives at a router for the local area network
            where the server is located. The web page you requested then travels
            back through the same routers to get to your browser. Inside the cloud
            labelled <q>Internet</q> in <xref ref="fig-inet"/> are additional routers. The job
            of all of these routers is to work together to get your information from
            place to place. You can see there are many routers for yourself if your
            computer supports the <c>traceroute</c> command. The text below shows
            the output of the <c>traceroute</c> command which illustrates that there
            are 13 routers between the web server at Luther College and the mail
            server at the University of Minnesota.</p>
        <pre>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</pre>
        <p>Each router on the Internet is connected to one or more other routers.
            So if you run the <c>traceroute</c> command at different times of the day,
            you are likely to see that your information flows through different
            routers at different times. This is because there is a cost associated
            with each connection between a pair of routers that depends on the
            volume of traffic, the time of day, and many other factors. By this time
            it will not surprise you to learn that we can represent the network of
            routers as a graph with weighted edges.</p>


        <figure align="center" xml:id="fig-network">
            <caption>Connections and Weights between Routers in the Internet.</caption>
                <image source="Graphs/routeGraph.png" width="80%">
                <description><p>The image displays a weighted graph that models the connections and weights between routers in the Internet. The graph consists of six nodes, each representing a router labeled as u, v, w, x, y, and z. The nodes are interconnected by lines that signify the network links between routers. Each line is annotated with a number, representing the weight of the connection, which could indicate the cost, distance, or quality of the link. For instance, router u is connected to router x with a weight of 2, and router x is connected to router v with a weight of 2 and to router y with a weight of 1. This type of graph is typically used to represent the efficiency of data transfer paths in network routing algorithms.</p></description>
                </image>
            </figure>
        <p><xref ref="fig-network"/> shows a small example of a weighted graph that
            represents the interconnection of routers in the Internet. The problem
            that we want to solve is to find the path with the smallest total weight
            along which to route any given message. This problem should sound
            familiar because it is similar to the problem we solved using a breadth
            first search, except that here we are concerned with the total weight of
            the path rather than the number of hops in the path. It should be noted
            that if all the weights are equal, the problem is the same.</p>
            <conclusion><p>
                <!-- extra space before the progress bar -->
            </p></conclusion>
    </section>