|
网上贸易 创造奇迹! 阿里巴巴 Alibaba Powered By Dvbbs Version 7.1.0 Copyright ©2003 - 2006 QTHome.Org 页面执行时间 00.12500 秒, 2 次数据查询 |
 |
| 以文本方式查看主题 - 趣题之家 (http://qthome.org/bbs/index.asp) -- 算法艺术 (http://qthome.org/bbs/list.asp?boardid=38) ---- 迪杰斯特拉算法 (http://qthome.org/bbs/dispbbs.asp?boardid=38&id=290) |
| -- 作者：remlostime -- 发布时间：3/15/2005 11:07:13 PM -- 迪杰斯特拉算法 迪杰斯特拉算法
本节将讨论带权有向图，并称路径上的第一个顶点为源点（soruse）, 最后一个顶点为终点（destination）。下面讲一种最常见的最短路径问题----从某个源点到其余各顶点的最短路径。
例： 1 4 2 2 2 3 3 3 ① ② ③ ④ ⑤ ⑥
program dijkstra; const max=6; of integer=((0, 3, 2, 100,100,100), (3, 100,100,2, 3, 100), (2, 100,100,4, 100,3), (100,2, 4, 100,100,2), (100,3, 100,100,100,1), (100,100,3, 2, 1, 100)); of integer; 存点1到各点的最短路径长度 of set of 1..max; 存点1到各点的最短路径集合 i,j,k,l,m,n:integer; q:set of 1..max; 已扩展的点的集合 begin l:=100; l：存当前最短的边，初值为100 for i:=1 to max do 初始化，存与点1相连的各点到点1的当前最短路径长度和路 begin 径集合 ss:=s[1,i];if ss<l then p:=[1]+ else p:=[] end; ; 已扩展点的集合初值 for k:=1 to max -1 do 循环max-1次，分别求点1到其余各点的最短路径 begin l:=100;j:=1; j:当前要扩展的点（初值为1） for i:=1 to max do 找当前要扩展的点j（边长最短的） if not(i in q) and (ss<l) then begin j:=i;l:=ss end; ; 扩展当前第j点 for i:=1 to max do 修正点1到各点的最短跟距离 <ss) then begin ss:=ss[j]+s[j,i];p:=p[j]+ end end; for i:=2 to max do 输出最短路径和距离 begin for j:=1 to max do if j in p then write(j:2); writeln(\'s=\':5,ss) end; end.
|
| -- 作者：licong -- 发布时间：3/21/2005 1:40:26 PM -- 我更喜欢Floyed 省事 |
| -- 作者：remlostime -- 发布时间：3/21/2005 2:59:02 PM -- 时间不够就要用，象noip应该可用FLOYED代替它 |
| -- 作者：gdgzgq -- 发布时间：3/22/2005 9:27:10 PM -- 恩，NOIP不会考太难的图论问题。 |
| -- 作者：HenryErnst -- 发布时间：3/28/2005 11:56:55 AM -- 这还叫难??????那什么叫简单? |
| -- 作者：趣题之主 -- 发布时间：4/2/2005 7:30:29 PM -- 确实，dijkstra是很基础的算法，NOIP中应该不用堆来优化，那就更基础了…… |
| -- 作者：nowords -- 发布时间：7/15/2005 11:07:27 AM -- DIJKSTRA是图论中最基础的算法之一,肯定是NOIP大纲要求 |
|
|||