📄 page567.html
字号:
<HTML><HEAD><TITLE>Implementation</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="tex2html7678" HREF="page568.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7676" HREF="page564.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7670" HREF="page566.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7680" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016413000000000000000">Implementation</A></H3><P>An implementation of Dijkstra's algorithmis shown in Program <A HREF="page567.html#progalgorithmsc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>DijkstrasAlgorithm</tt> method takes two arguments.The first is a directed graph.It is assumed that the directed graph is an edge-weighted graphin which the weights are <tt>int</tt>s.The second argument is the number of the start vertex, <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline71415" SRC="img2332.gif" >.<P>The <tt>DijkstrasAlgorithm</tt> method returns its resultin the form of a shortest-path graph.Therefore, the return value is a <tt>Digraph</tt> instance.<P><P><A NAME="51980"> </A><A NAME="progalgorithmsc"> </A> <IMG WIDTH=575 HEIGHT=603 ALIGN=BOTTOM ALT="program51977" SRC="img2370.gif" ><BR><STRONG>Program:</STRONG> Dijkstra's algorithm.<BR><P><P>The main data structures used are called<tt>table</tt> and <tt>queue</tt> (lines 5 and 9).The former is an array of <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71839" SRC="img2371.gif" > <tt>Entry</tt> elements.The latter is a priority queue.In this case,a <tt>BinaryHeap</tt> of length <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70987" SRC="img2251.gif" > is used.(See Section <A HREF="page353.html#secpqueuesbinheaps"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P>The algorithm begins by setting the tentative distance for the startvertex to zero and inserting the start vertex into the priorityqueue with priority zero (lines 8-10).<P>The main loop of the method comprises lines 11-23.In each iteration of this loop the vertex with the smallest distanceis dequeued (line 12).The vertex is processed only if its table entryindicates that the shortest path is not already known (line 14).<P>When a vertex <tt>v0</tt> is processed,its shortest path is deemed to be <em>known</em> (line 15).Then each vertex <tt>v1</tt> adjacent to vertex is considered (lines 16-23).The distance to <tt>v1</tt> along the path that passes through <tt>v0</tt>is computed (line 18).If this distance is less than the tentative distanceassociated with <tt>v1</tt>,entries in the table for <tt>v1</tt> are updated,and the <tt>v1</tt> is given a new priorityand inserted into the priority queue (lines 19-23).<P>The main loop terminates when all the shortest paths have been found.The shortest-path graph is thenconstructed using the information in the table (lines 24-29).<P><HR><A NAME="tex2html7678" HREF="page568.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7676" HREF="page564.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7670" HREF="page566.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7680" 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 + -