📄 page563.html
字号:
<HTML><HEAD><TITLE>Shortest-Path Algorithms</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7628" HREF="page564.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7626" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7620" HREF="page562.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7630" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0016400000000000000000">Shortest-Path Algorithms</A></H1><P>In this section we consider edge-weighted graphs,both directed and undirected,in which the weight measures the <em>cost</em> of traversing that edge.The units of cost depend on the application.<P>For example, we can use a directed graph to represent a network of airports.In such a graph the vertices represent the airportsand the edges correspond to the available flights between airports.In this scenario there are several possible cost metrics:If we are interested in computing travel time,then we use an edge-weighted graph in which the weights representthe flying time between airports.If we are concerned with the financial cost of a trip,then the weights on the edges represent the monetary cost of a ticket.Finally, if we are interested the actual distance traveled,then the weights represent the physical distances between airports.<P>If we are interested in traveling from point <I>A</I> to <I>B</I>,we can use a suitably labeled graph to answer the following questions:What is the fastest way to get from <I>A</I> to <I>B</I>?Which route from <I>A</I> to <I>B</I> has the least expensive airfare?What is the shortest possible distance traveled to get from <I>A</I> to <I>B</I>?<P>Each of these questions is an instance of the same problem:Given an edge-weighted graph, <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >,and two vertices, <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71411" SRC="img2330.gif" > and <IMG WIDTH=46 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71413" SRC="img2331.gif" >,find the path that starts at <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif" > and ends at <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71417" SRC="img2333.gif" >that has the smallest weighted path length.The weighted length of a path is defined as follows:<P><BLOCKQUOTE> <b>Definition (Weighted Path Length)</b><A NAME="defngraphswpl"> </A>Consider an edge-weighted graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >.Let <IMG WIDTH=57 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline71421" SRC="img2334.gif" > be the weight on the edge connecting <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif" > to <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline71257" SRC="img2299.gif" >.A path in <I>G</I> is a non-empty sequence of vertices <IMG WIDTH=137 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70709" SRC="img2199.gif" >.The <em>weighted path length</em><A NAME=51334> </A><A NAME=51335> </A>of path <I>P</I> is given by<P> <IMG WIDTH=301 HEIGHT=47 ALIGN=BOTTOM ALT="displaymath71391" SRC="img2335.gif" ><P></BLOCKQUOTE><P>The <em>weighted</em> length of a path is the sum of the weightson the edges in that path.Conversely, the <em>unweighted</em> length of a pathis simply the number of edges in that path.Therefore,the <em>unweighted</em> length of a path is equivalent tothe weighted path length obtained when all edge weights are one.<P><BR> <HR><UL> <LI> <A NAME="tex2html7631" HREF="page564.html#SECTION0016410000000000000000">Single-Source Shortest Path</A><LI> <A NAME="tex2html7632" HREF="page569.html#SECTION0016420000000000000000">All-Pairs Source Shortest Path</A></UL><HR><A NAME="tex2html7628" HREF="page564.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7626" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7620" HREF="page562.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7630" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -