📄 dij-op.html

📁 Data Structure Ebook
💻 HTML
字号:
<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Dijkstra's Algorithm - operation</TITLE>

<META name="description" content="Data Structures and Algorithms Course Notes,
PLDS210 University of Western Australia">
<META name="keywords" content="data structures,algorithms,abstract data types ">
</HEAD>
<BODY BGCOLOR="#ffffff">
<TABLE BGCOLOR="#00c0f0" WIDTH="100%" CELLSPACING=0 CELLPADDING=0>
<TR BGCOLOR="#00f0f0"><TD ALIGN=right>
<FONT FACE=helvetica SIZE=+1><I>Data Structures and Algorithms</I></FONT>
</TD></TR>

<TR><TD><FONT FACE=helvetica SIZE=+2><B>Operation of Dijkstra's Algorithm</B></FONT>
</TD></TR>
</TABLE>
<P>
This sequence of diagrams illustrates the operation of Dijkstra's
Algorithm.

<TABLE BORDER=1>
<TR><TD><IMG SRC="dij1.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/dij1.gif"></TD>
<TD>Initial graph<BR>
All nodes have infinite cost except the source</TD>
</TR>
<TR><TD><IMG SRC="dij2.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/dij2.gif"></TD>
<TD>Choose the closest node to <B>s</B>.
<P>
As we initialised d[s] to 0, it's <B>s</B>.
<P>
Add it to <B>S</B>
<P>
Relax all nodes adjacent to <B>s</B>.
<P>
Update predecessor (red arrows) for all
nodes updated.
</TR>
<TR><TD><IMG SRC="dij3.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/dij3.gif"></TD>
<TD>Choose the closest node, <B>x</B>
<P>Relax all nodes adjacent to <B>x</B>
<P>Update predecessors for <B>u, v</B> and <B>y</B>.
</TD>
</TR>
<TR><TD><IMG SRC="dij4.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/dij4.gif"></TD>
<TD>Now <B>y</B> is the closest,
add it to <B>S</B>.
<P>Relax <B>v</B> and adjust its
predecessor.
</TR>
<TR><TD><IMG SRC="dij5.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/dij5.gif"></TD>
<TD><B>u</B> is now closest,
choose it and adjust its neighbour,
<B>v</B>.
</TD>
<TR><TD><IMG SRC="dij6.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/dij6.gif"></TD>
<TD>Finally, add <B>v</B>.
<P>
The predecessor list now defines the
shortest path from each node to <B>s</B>.
</TD>
</TR>
</TABLE>


<P>

<TABLE CELLPADDING=5 WIDTH="100%" BGCOLOR="#00f0f0" CELLSPACING=4>
<TR><TD WIDTH=50%>
Back to <A HREF="dijkstra.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/dijkstra.html">Dijkstra's Algorithm</A></TD>
<TD>Back to the <A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
</TD></TR></TABLE>
<SMALL>
&copy; <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1998
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明

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