头衔：ENDLESS
等级：版主
文章：36
积分：116
注册：2004-11-24 |
 迪杰斯特拉算法
迪杰斯特拉算法
本节将讨论带权有向图，并称路径上的第一个顶点为源点（soruse）, 最后一个顶点为终点（destination）。下面讲一种最常见的最短路径问题----从某个源点到其余各顶点的最短路径。
例：
14222333①②③④⑤⑥
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.
|
|
|
|
注册
趣题之家 → 信息学竞赛 → 算法艺术 → 迪杰斯特拉算法
2005-03-15 23:07
