page564.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 102 行

HTML
102 行
字号 
<HTML><HEAD><TITLE>Single-Source Shortest Path</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="tex2html7641" HREF="page565.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7639" HREF="page563.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7633" HREF="page563.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7643" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0016410000000000000000">Single-Source Shortest Path</A></H2><P>In this section we consider the <em>single-source shortest path</em> problem:Given an edge-weighted graph  <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif"  > and a vertex  <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71411" SRC="img2330.gif"  >,find the shortest weighted path from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to every other vertex in  <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif"  >.<P>Why do we find the shortest path to every other vertexif we are interested only in the shortest path from,say,  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71417" SRC="img2333.gif"  >?It turns out that in order to find the shortest path from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71417" SRC="img2333.gif"  >,it is necessary to find the shortest path from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  >to every other vertex in <I>G</I>!If a vertex is ignored, say  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif"  >,then we will not consider any of the paths from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71417" SRC="img2333.gif"  >that pass through  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif"  >.But if we fail to consider all the paths from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71417" SRC="img2333.gif"  >,we cannot be assured of finding the shortest one.<P>Furthermore, suppose the shortest path from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71417" SRC="img2333.gif"  >passes through some intermediate node  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif"  >.That is, the shortest path is of the form  <IMG WIDTH=166 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71471" SRC="img2336.gif"  >It must be the case that the portion of <I>P</I> between  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif"  >is also the shortest path from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif"  >.Suppose it is not.Then there exists another shorter path from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif"  >.But then, <I>P</I> would not be the shortest path from  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > to  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71417" SRC="img2333.gif"  >,because we could obtain a shorter one by replacing the portionof <I>P</I> between  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif"  > and  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif"  > by the shorter path.<P>Consider the directed graph  <IMG WIDTH=24 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71499" SRC="img2337.gif"  > shown in Figure&nbsp;<A HREF="page564.html#figgraph12"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The shortest <em>weighted</em> path between vertices <I>b</I> and <I>f</I> is the path <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71505" SRC="img2338.gif"  >which has the weighted path length nine.On the other hand, the shortest <em>unweighted</em> path is from <I>b</I> to <I>f</I> isthe path of length three,  <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71511" SRC="img2339.gif"  >.<P><P><A NAME="51597">&#160;</A><A NAME="figgraph12">&#160;</A> <IMG WIDTH=575 HEIGHT=181 ALIGN=BOTTOM ALT="figure51349" SRC="img2340.gif"  ><BR><STRONG>Figure:</STRONG> Two edge-weighted directed graphs.<BR><P><P>As long as all the edge weights are non-negative(as is the case for  <IMG WIDTH=24 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71499" SRC="img2337.gif"  >),the shortest-path problem is well defined.Unfortunately, things get a little trickyin the presence of negative edge weights.<P>For example, consider the graph  <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71523" SRC="img2341.gif"  > shown in Figure&nbsp;<A HREF="page564.html#figgraph12"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Suppose we are looking for the shortest path from <I>d</I> to <I>f</I>.Exactly two edges emanate from vertex <I>d</I>,both with the same edge weight of five.If the graph contained only positive edge weights,there could be no shorter path than the direct path  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71531" SRC="img2342.gif"  >.<P>However, in a graph that contains negative weights,a long path gets ``shorter'' when we add edges with negative weights to it.For example, the path  <IMG WIDTH=84 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71533" SRC="img2343.gif"  > has a total weighted path length of four,even though the first edge, (<I>d</I>,<I>a</I>), has the weight five.<P>But negative weights are even more insidious than this:For example, the path  <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71537" SRC="img2344.gif"  >,which also joins vertex <I>d</I> to <I>f</I>,has a weighted path length of twobut the path  <IMG WIDTH=159 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71543" SRC="img2345.gif"  > has length zero.That is, as the number of edges in the path increases,the weighted path length decreases!The problem in this case is the existence of the cycle  <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71545" SRC="img2346.gif"  >the weighted path length of which is less than zero.Such a cycle is called a <em>negative cost cycle</em><A NAME=51604>&#160;</A><A NAME=51605>&#160;</A>.<P>Clearly, the shortest-path problem is not definedfor graphs that contain negative cost cycles.However, negative edges are not intrinsically bad.Solutions to the problem do existfor graphs that contain both positive and negative edge weights,as long as there are no negative cost cycles.Nevertheless, the problem is greatly simplifiedwhen all edges carry non-negative weights.<P><BR> <HR><UL> <LI> <A NAME="tex2html7644" HREF="page565.html#SECTION0016411000000000000000">Dijkstra's Algorithm</A><LI> <A NAME="tex2html7645" HREF="page566.html#SECTION0016412000000000000000">Data Structures for Dijkstra's Algorithm</A><LI> <A NAME="tex2html7646" HREF="page567.html#SECTION0016413000000000000000">Implementation</A><LI> <A NAME="tex2html7647" HREF="page568.html#SECTION0016414000000000000000">Running Time Analysis</A></UL><HR><A NAME="tex2html7641" HREF="page565.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7639" HREF="page563.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7633" HREF="page563.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7643" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page564.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page564.html 源码文件，采用 HTML 编程语言编写，共 102 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?