📄 算法.htm
字号:
<legend><a style="font-weight:bold; color:#FF0000" href="misc.php?action=viewratings&tid=56497&pid=307955" title="查看评分记录">本帖最近评分记录</a></legend>
<ul>
<div id="post_rate_307955"></div> <li>
<cite><a style="color:#800000" href="space.php?uid=63517" target="_blank">花如月</a></cite>
<font color="#8000FF">威望</font>
<strong><font color="#FF0000">+1</font></strong>
<font color="#008000">2008-1-1 14:50</font>
<em>理由：<font color="#0000FF">经验分享</font></em>
</li>
</ul>
</fieldset>
</div>
<div class="signatures" style="maxHeightIE: 60px;">
欢迎访问我的blog：<br />
7752577.blog.sohu.com<br />
有很多好程序哦 </div>
</td>
</tr>
<tr>
<td class="postauthor">
<div class="popupmenu_popup userinfopanel" id="userinfo307955_menu" style="display: none;">
<dl><dt>UID</dt><dd>17385 </dd><dt>帖子</dt><dd>133 </dd><dt>精华</dt><dd><a href="digest.php?authorid=17385">1</a> </dd><dt>积分</dt><dd>32 </dd><dt>体能</dt><dd>10 点 </dd><dt>威望</dt><dd>17 点 </dd><dt>管理积分</dt><dd>0 点 </dd><dt>阅读权限</dt><dd>40 </dd><dt>在线时间</dt><dd>36 小时 </dd><dt>注册时间</dt><dd>2006-4-1 </dd><dt>最后登录</dt><dd>2008-1-19 </dd></dl>
<p><a href="space-uid-17385.html" target="_blank">查看详细资料</a></p>
</div>
</td>
<td class="postcontent">
<div class="postactions">
<p>
<strong onclick="scroll(0,0)" title="顶部">TOP</strong>
</p>
<div id="ad_thread1_1"></div> </div>
</td>
</tr>
</table>
</div>
<div class="mainbox viewthread">
<table id="pid308252" summary="pid308252" cellspacing="0" cellpadding="0">
<tr>
<td class="postauthor">
<cite> <a href="space-uid-17385.html" target="_blank" id="userinfo308252" class="dropmenu" onmouseover="showMenu(this.id)">assist</a></cite>
<div class="avatar"><img src="http://www.chinavib.com/ucenter/data/avatar/000/01/73/85_avatar_middle.jpg" onerror="this.onerror=null;this.src='http://www.chinavib.com/ucenter/images/noavatar_middle.gif'"></div> <p><em><font color="#4444BB">风流才子</font></em></p>
<p><img src="images/wld61/star_level2.gif" alt="Rank: 6" /><img src="images/wld61/star_level1.gif" alt="Rank: 6" /><img src="images/wld61/star_level1.gif" alt="Rank: 6" /></p>
<ul>
<li class="space"><a href="http://www.chinavib.com/UChome/space.php?uid=17385" target="_blank">个人空间</a></li>
<li class="pm"><a href="###" onclick="pmwin('open', 'uid=17385')">发短消息</a></li>
<li class="buddy"><a href="my.php?item=buddylist&newbuddyid=17385&buddysubmit=yes" target="_blank" id="ajax_buddy_2" onclick="ajaxmenu(event, this.id, 3000, 0)">加为好友</a></li>
<li class="offline">当前离线
</li>
</ul>
</td>
<td class="postcontent" >
<div class="postinfo">
<strong title="复制帖子链接到剪贴板" id="postnum308252" onclick="setcopy('http://www.chinavib.com/forum/viewthread.php?tid=56497&page=1#pid308252', '帖子链接已经复制到剪贴板')">板凳</strong>
<em onclick="$('postmessage_308252').className='t_bigfont'">大</em> <em onclick="$('postmessage_308252').className='t_msgfont'">中</em>
<em onclick="$('postmessage_308252').className='t_smallfont'">小</em> 发表于 2008-1-2 18:23 <a href="viewthread.php?tid=56497&page=1&authorid=17385" rel="nofollow">只看该作者</a>
</div>
<div id="ad_thread2_2"></div> <div class="postmessage defaultpost">
<div id="ad_thread3_2"></div><div id="ad_thread4_2"></div>
<h2>【转】Dijkstra算法说明</h2>
<div id="postmessage_308252" class="t_msgfont"><span font-size: 14px; id="236">Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。<br />
<br />
举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。<br />
<br />
Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。<br />
<br />
算法描述<br />
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候没条边(u,v)都只被拓展一次。<br />
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。 <br />
在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d值的顶点u。这个顶点被从集合Q中删除并返回给用户。<br />
1 function Dijkstra(G, w, s)<br />
2 for each vertex v in V[G] // 初始化<br />
3 d[v] := infinity<br />
4 previous[v] := undefined<br />
5 d[s] := 0<br />
6 S := empty set<br />
7 Q := set of all vertices<br />
8 while Q is not an empty set // Dijstra算法主体<br />
9 u := Extract_Min(Q)<br />
10 S := S union {u}<br />
11 for each edge (u,v) outgoing from u<br />
12 if d[v] > d + w(u,v) // 拓展边(u,v)<br />
13 d[v] := d + w(u,v)<br />
14 previous[v] := u<br />
如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。<br />
现在我们可以通过迭代来回溯出s到t的最短路径<br />
1 S := empty sequence <br />
2 u := t<br />
3 while defined u <br />
4 insert u to the beginning of S<br />
5 u := previous<br />
现在序列S就是从s到t的最短路径的顶点集.<br /><br />[<i> 本帖最后由 assist 于 2008-1-2 18:24 编辑 </i>]</span></div>
<div id="post_rate_div_308252"></div>
</div>
<div class="signatures" style="maxHeightIE: 60px;">
欢迎访问我的blog：<br />
7752577.blog.sohu.com<br />
有很多好程序哦 </div>
</td>
</tr>
<tr>
<td class="postauthor">
<div class="popupmenu_popup userinfopanel" id="userinfo308252_menu" style="display: none;">
<dl><dt>UID</dt><dd>17385 </dd><dt>帖子</dt><dd>133 </dd><dt>精华</dt><dd><a href="digest.php?authorid=17385">1</a> </dd><dt>积分</dt><dd>32 </dd><dt>体能</dt><dd>10 点 </dd><dt>威望</dt><dd>17 点 </dd><dt>管理积分</dt><dd>0 点 </dd><dt>阅读权限</dt><dd>40 </dd><dt>在线时间</dt><dd>36 小时 </dd><dt>注册时间</dt><dd>2006-4-1 </dd><dt>最后登录</dt><dd>2008-1-19 </dd></dl>
<p><a href="space-uid-17385.html" target="_blank">查看详细资料</a></p>
</div>
</td>
<td class="postcontent">
<div class="postactions">
<p>
<strong onclick="scroll(0,0)" title="顶部">TOP</strong>
</p>
<div id="ad_thread1_2"></div> </div>
</td>
</tr>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -