page565.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 105 行 · 第 1/2 页

(as is the case for  <IMG WIDTH=24 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72297" SRC="img2446.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2446.gif"  >),
the shortest-path problem is well defined.
Unfortunately, things get a little tricky
in the presence of negative edge weights.
<P>
For example, consider the graph  <IMG WIDTH=24 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72321" SRC="img2450.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2450.gif"  > shown in Figure&nbsp;<A HREF="page565.html#figgraph12" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page565.html#figgraph12"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72329" SRC="img2451.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2451.gif"  >.
<P>
However, in a graph that contains negative weights,
a long path gets ``shorter'' when we add edges with negative weights to it.
E.g., the path  <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72331" SRC="img2452.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2452.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=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72335" SRC="img2453.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2453.gif"  >,
which also joins vertex <I>d</I> to <I>f</I>,
has a weighted path length of two
but the path  <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72341" SRC="img2454.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2454.gif"  > has length zero.
I.e., 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_inline72343" SRC="img2455.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2455.gif"  >
the weighted path length of which is less than zero.
Such a cycle is sometimes called a <em>negative cost cycle</em><A NAME=51704>&#160;</A><A NAME=51705>&#160;</A>.
<P>
Clearly, the shortest-path problem is not defined
for graphs that contain negative cost cycles.
However, negative edges are not intrinsically bad.
Solutions to the problem do exist
for graphs that contain both positive and negative edge weights,
as long as there are no negative cost cycles.
Nevertheless, the problem is greatly simplified
when all edges carry non-negative weights.
<P>
<BR> <HR>
<UL> 
<LI> <A NAME="tex2html8898" HREF="page566.html#SECTION0017411000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page566.html#SECTION0017411000000000000000">Dijkstra's Algorithm</A>
<LI> <A NAME="tex2html8899" HREF="page567.html#SECTION0017412000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page567.html#SECTION0017412000000000000000">Data Structures for Dijkstra's Algorithm</A>
<LI> <A NAME="tex2html8900" HREF="page568.html#SECTION0017413000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page568.html#SECTION0017413000000000000000">Implementation</A>
<LI> <A NAME="tex2html8901" HREF="page569.html#SECTION0017414000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page569.html#SECTION0017414000000000000000">Running Time Analysis</A>
</UL>
<HR><A NAME="tex2html8894" HREF="page566.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page566.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8892" HREF="page564.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page564.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8886" HREF="page564.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page564.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8896" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8897" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>