?? dijikstra.htm
字號:
<!--Header-->
<HTML>
<HEAD>
<TITLE>GPMega - Advanced Section - Shortest Paths: Dijkstra's Algorithm</TITLE>
</HEAD>
<BODY BGCOLOR=#000000 TEXT=#FFFFFF LINK=#00FF00 VLINK=#00FF00 ALINK=#0000FF>
<!--End Header-->
<!--Advertiser-->
<CENTER>
<TABLE>
<TR>
<TD>
<A HREF="http://www.ugo.com/">
<IMG SRC="/GPMega/ugologo120.gif" BORDER=0 WIDTH=120 HEIGHT=60></A>
</TD>
<TD>
<IMG SRC="/GPMega/sponsored.gif" WIDTH=468 HEIGHT=10><br><br>
<SCRIPT LANGUAGE= "JavaScript">
<!--
var now = new Date();
var random_num = now.getSeconds();
document.write("<A HREF='http://www.ugo.net/RealMedia/ads/click_nx.cgi/www.perplexed.com/GPMega/advanced/dijikstra.htm/" + random_num + "/@Top'>");
document.write("<IMG SRC='http://www.ugo.net/RealMedia/ads/adstream_nx.cgi/www.perplexed.com/GPMega/advanced/dijikstra.htm/" + random_num + "/@Top' BORDER='0' WIDTH='468' HEIGHT='60'></A>");
//-->
</SCRIPT>
</TD>
</TR>
</TABLE>
</CENTER>
<!--End Advertiser-->
<!--Splitter-->
<BR>
<!--End Splitter-->
<!--Body-->
<FONT SIZE=2 FACE=Helvetica>
<STRONG>
<!--Top Navigation-->
<A NAME="top"></A>
<CENTER>
<TABLE WIDTH=75%>
<TR VALIGN=MIDDLE>
<TD ALIGN=LEFT>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1><BR><BR>
<A HREF="http://www.perplexed.com/GPMega/"><IMG SRC="logo.jpg" BORDER=0 ALT="Home" WIDTH=80 HEIGHT=47 ALIGN=CENTER></A>
<FONT COLOR=#666666 FACE=HELVETICA SIZE=-1><I>
This Article Is Taken From <A HREF="http://www.perplexed.com/GPMega/">The Game Programming MegaSite</A>, A Definitive Resource For Game Developers!
</I></FONT><BR>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1>
</TD>
</TR>
</TABLE>
</CENTER>
<BR><!--End Top Navigation-->
<!--Title-->
<H3 ALIGN=CENTER><font color="#FFF800">S</font><font color="#FFF100">h</font><font color="#FFEA00">o</font><font color="#FFE300">r</font><font color="#FFDC00">t</font><font color="#FFD500">e</font><font color="#FFCE00">s</font><font color="#FFC700">t</font><font color="#FFC000"> </font><font color="#FFB900">P</font><font color="#FFB200">a</font><font color="#FFAB00">t</font><font color="#FFA400">h</font><font color="#FF9D00">s</font><font color="#FF9600">:</font><font color="#FF8F00"> </font><font color="#FF8800">D</font><font color="#FF8100">i</font><font color="#FF7A00">j</font><font color="#FF7300">k</font><font color="#FF6C00">s</font><font color="#FF6500">t</font><font color="#FF5E00">r</font><font color="#FF5700">a</font><font color="#FF5000">'</font><font color="#FF4900">s</font><font color="#FF4200"> </font><font color="#FF3B00">A</font><font color="#FF3400">l</font><font color="#FF2D00">g</font><font color="#FF2600">o</font><font color="#FF1F00">r</font><font color="#FF1800">i</font><font color="#FF1100">t</font><font color="#FF0A00">h</font><font color="#FF0300">m</font><BR><FONT SIZE=-2>By: <A HREF="mailto:crpalmer@undergrad.math.uwaterloo.ca">Chris Palmer</A></FONT></H3>
<!--End Title-->
<H3><FONT COLOR=YELLOW><I>Notes:</I></FONT></H3>
<P>This algorithm is not presented in the same way that you'll find it in most texts because i'm ignored directed vs. undirected graphs and i'm ignoring the loop invariant that you'll see in any book which is planning on proving the correctness of the algorithm.
<P>If we are dealing with a di-graph the algorithm will be the same with the only difference being the meaning attached to each edge.
<P>The loop invariant is that at any stage we have partitioned the graph into three sets of vertices (S,Q,U), S which are vertices to which we know their shortest paths, Q which are ones we have "queued" knowing that we may deal with them now and U which are the other vertices. This information is important in proving the correctness and analyzing the running-time of the algorithm and not for understanding it (in my humble opinion).
<BLOCKQUOTE>
<FONT COLOR=RED>
<DL>
<DT><I>REF</I>: Cormen. Thomas H., Leiserson, Charles E., Rivest, Ronald L.,
<DD><I>Introduction to Algorithms</I>, MIT Press (1990), pages 527-531
</DL>
</FONT>
</BLOCKQUOTE>
<H3><FONT COLOR=YELLOW><I>Revision:</I></FONT></H3>
<P>The current revision of this page was last modified on November 18th, 1995.
<P>Given a graph G with a weight function wt:E(G)->R which maps the edges
to a real valued weight and wt(e) > 0 for all e in E(G). NOTE: wt(e) > 0
is a VERY important assumption. As i've presented the algorith, a weight
of 0 is not actually a problem (it could be for some implementations) but
a negative weight could/would result in an infinite loop. For example,
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
*---- 1 ---*
\ /
-10 1
\ /
\ /
*
</FONT></PRE>
</BLOCKQUOTE>
<P>will generate paths which cycle endlessly.
<P>You need an origin vertex (where all the paths are starting from, or,
more typically in games, where the paths are ending).
<P>Augment the labels of the vertices by a real value, initially infinity,
which is the shortest weighted path from the origin to this vertex (which
has been found so far). Also, augment each vertex with a "pointer" to its
parent in the shortest weighted path found so far, initially have this
pointing nowhere.
<P>You need a priority queue which is sorted based on the weight of the
shortest path from the origin to the vertex. When an element is inserted
into the priority queue and it already exists, the previous copy must be
removed and the new one inserted into the right level [*].
<P>Take the origin vertex, set the weight of the shortest path to 0 and
push it onto the priority queue.
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
while the priority queue is not empty, pop an entry <v,w_v,p_v> where
v is the vertex, w_v and p_v are the augmented labels of v.
foreach edge e=(v,u) in G, where u has augmented labels w_u, p_u.
if wt(e) + w_v < w_u then
set p_u to v
set w_u to wt(e) + w_v
add <u, w_u, p_u> to the priority queue.
</FONT></PRE>
</BLOCKQUOTE>
<H3><FONT COLOR=YELLOW><I>Comments:</I></FONT></H3>
<P>Technically, [*] must be true because otherwise it would be impossible to
prove the correctness of the algorithm. I've played with an personally
think that you can get a better performance (your priority queue becomes
almost O(1) with the cost of extra elements building up in the queue)
by relaxing this restriction and allowing multiple copies of the same
vertex to accumulate in the queue.
<P>The net effect will be that some sets of vertices may have to be cycled
through the queue several times (read "more cost"). It is my opinion
that this additional cost is considerably less than the O(log n) [n is
the size of the priority queue] time required to implement this algorithm
as described above.
<P>However, I have not attempted to analyze the worst case effect of relaxing
[*] and would say to implement it in this way only if you trust my guess.
<P>Also, note that if you were going to implement a heuristic for directing
the search, you wouldn't insert the weight of the shortest path from the
source node to this node. Instead, you would insert the weight of the
shortest path from the source node to this node plus the heuristic's
estimate of the cost to the destination node. I won't be discussing this
anymore until the very end of the document.
<H3><FONT COLOR=YELLOW><I>Tile/Grid Implementation:</I></FONT></H3>
<BLOCKQUOTE>
<FONT COLOR=RED>
<DL>
<DT><I>Def</I>: What I mean by "a game with a grid/tile map"
<DD>A game where the playing area is dividing into squares with one or more "object" on the square. These objects include walls, doors, etc which are assumed to occupy the entire square.
</DL>
</FONT>
</BLOCKQUOTE>
<P>If you want to apply what i'm going to say where walls do not occupy the
entire square, you'll need a function wt({x,y}, {x',y'}) which gives the
cost of moving from (x,y) to (x',y') and otherwise it's the same.
<P>In a game with a grid map, you need a function (or a table or whatever)
which i'll call wt(x,y) which gives you the "cost" of moving onto a
specified grid location (x,y). Note: "moving *onto*". If you are
writing a dungeon based game and you have a teleporter at (a,b) that you don't
want the monsters to hit, make wt(a,b) = infinity where infinity is
some arbitrarily large number. The same applies to walls, if you have a
wall square at (a,b) then wt(a,b) = infinity.
<P>For any square, there are at most 8 squares around it. This is easy to
implement with an array that gives the offsets for each square.
<P>We'll assume that you don't want the shortest paths for the entire world
(which could be arbitrarily large) but instead want shortest paths for
only a limited area, say of width and height 2*DELTA+1.
<P>We will be storing elements in two arrays in positions [0..2*DELTA] which
correspond to the position on the map (o_x - x + DELTA - 1). To make
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -