Dijkstra 堆优化 PASCAL

来源：百度知道 编辑：UC知道 时间：2024/06/22 01:35:32
NOCOW上的看不懂，谁来救救我
给我讲明原理即可{每次怎么取最小值、去后怎么更新}
最好附上代码
好的+50
我听我同学说二叉堆中的点{非根节点}是不能向下调整的，所以我才写不下去的。
这位大牛确定可以向下调整

给你看个源程序
program SSSP;{single source shortest path}
{假设一个图的最大节点数为1000，所有运算在integer范围内}
{程序目标：给定有向图的邻接表，求出节点1到节点n的最短路径长度}
const maxn=1000;{最大节点数}
var
n:integer;{节点个数}
deg:array[1..maxn] of integer;{每个节点的度数}
list:array[1..maxn,1..maxn,1..2] of integer;{邻接表，第一个元素表示边的中点，第二个元素表示边的长度}

count:integer;{堆内元素个数计数器}
heap:array[1..maxn] of integer;{heap[i]表示堆内的第i的元素的节点编号}
pos:array[1..maxn] of integer;{表示编号为i的元素在堆内的位置}
key:array[1..maxn] of integer;{表示节点1到节点i的最短距离}
exist:array[1..maxn] of boolean;{表示节点i是否存在于堆中}

i,j,now:integer;

procedure swap(var i,j:integer);{交换整数i和j}
var temp:integer;
begin
temp:=i;
i:=j;
j:=temp;
end;

procedure heapify(p:integer);{调整堆的过程}
var best:integer;
begin
best:=p;
if (p*2<=count) and (key[heap[p*2]]<key[heap[best]]) then best:=p*2;
if (p*2+1<=count) and (key[heap[p*2+1]]<key[heap[best]]) th