page565.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 182 行 · 第 1/2 页
HTML
182 行
<HTML><HEAD><TITLE>Dijkstra's Algorithm</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="tex2html7656" HREF="page566.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7654" HREF="page564.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7648" HREF="page564.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7658" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016411000000000000000">Dijkstra's Algorithm</A></H3><A NAME="secgraphsdijkstra"> </A><P><em>Dijkstra's algorithm</em><A NAME=51609> </A>is a greedy algorithm for solvingthe single-source, shortest-path problem on an edge-weighted graphin which all the weights are non-negative.It finds the shortest paths from some initial vertex, say <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif" >,to all the other vertices one-by-one.The essential feature of Dijkstra's algorithmis the order in which the paths are determined:The paths are discovered in the order of their weighted lengths,starting with the shortest, proceeding to the longest.<P>For each vertex <I>v</I>,Dijkstra's algorithm keeps track of three pieces of information, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71551" SRC="img2347.gif" >, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71553" SRC="img2348.gif" >, and <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71555" SRC="img2349.gif" >:<DL ><DT><STRONG> <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71551" SRC="img2347.gif" ></STRONG><DD> The <tt>bool</tt>-valued flag <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71551" SRC="img2347.gif" > indicates that the shortest path to vertex <I>v</I> is <em>known</em>. Initially, <IMG WIDTH=78 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71563" SRC="img2350.gif" > for all <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71565" SRC="img2351.gif" >. <DT><STRONG> <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71553" SRC="img2348.gif" ></STRONG><DD> The quantity <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71553" SRC="img2348.gif" > is the length of the shortest known path from <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif" > to <I>v</I>. When the algorithm begins, no shortest paths are known. The distance <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71553" SRC="img2348.gif" > is a <em>tentative</em> distance. During the course of the algorithm candidate paths are examined and the <em>tentative</em> distances are modified.<P> Initially, <IMG WIDTH=52 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71577" SRC="img2352.gif" > for all <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71565" SRC="img2351.gif" > such that <IMG WIDTH=43 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline71581" SRC="img2353.gif" >, while <IMG WIDTH=51 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline71583" SRC="img2354.gif" >. <DT><STRONG> <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71555" SRC="img2349.gif" ></STRONG><DD> The predecessor of vertex <I>v</I> on the shortest path from <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif" > to <I>v</I>. That is, the shortest path from <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif" > to <I>v</I> has the form <IMG WIDTH=95 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71597" SRC="img2355.gif" >.<P> Initially, <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71555" SRC="img2349.gif" > is unknown for all <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71565" SRC="img2351.gif" >.<P> </DL><P>Dijkstra's algorithm proceeds in phases.The following steps are performed in each pass:<OL><LI> From the set of vertices for with <IMG WIDTH=78 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71563" SRC="img2350.gif" >, select the vertex <I>v</I> having the smallest tentative distance <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71553" SRC="img2348.gif" >.<LI> Set <IMG WIDTH=73 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71609" SRC="img2356.gif" >.<LI> For each vertex <I>w</I> adjacent to <I>v</I> for which <IMG WIDTH=73 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline71615" SRC="img2357.gif" >, test whether the tentative distance <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71617" SRC="img2358.gif" > is greater than <IMG WIDTH=86 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71619" SRC="img2359.gif" >. If it is, set <IMG WIDTH=129 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71621" SRC="img2360.gif" > and set <IMG WIDTH=53 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline71623" SRC="img2361.gif" >.</OL>In each pass exactly one vertex has its <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71551" SRC="img2347.gif" > set to <tt>True</tt>.The algorithm terminates after <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif" > passes are completedat which time all the shortest paths are known.<P>Table <A HREF="page565.html#tblgraphsdijkstra"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the operation of Dijkstra'salgorithm as it finds the shortest paths starting from vertex <I>b</I>in graph <IMG WIDTH=24 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71499" SRC="img2337.gif" > shown in Figure <A HREF="page564.html#figgraph12"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="51628"> </A><P> <A NAME="tblgraphsdijkstra"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=36 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=35> passes</TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><P> vertex </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> initially</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> 1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> 2</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> 3</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> 4</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> 5</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> 6</TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>a</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=13 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline71639" SRC="img2362.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=13 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline71639" SRC="img2362.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=13 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline71639" SRC="img2362.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=13 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline71639" SRC="img2362.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=13 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline71639" SRC="img2362.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> --⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?