单源最短路径 mapreduce

program dijkstra;
const
inf = '';
outf = '';
maxn = 100;

var
n, s, t: longint;
judge: array[1..maxn] of boolean;
dis: array[1..maxn] of longint;
a: array[1..maxn, 1..maxn] of longint;

procedure assignfile;
begin
assign(input, inf); reset(input);
assign(output, outf); rewrite(output);
end;

procedure closefile;
begin
close(input); close(output);
end;

procedure init;
var
i, j: longint;
begin
readln(n);
for i := 1 to n do begin
for j := 1 to n do read(a[i, j]);
readln;
end;
readln(s, t);
end;

procedure process;
var
now, i: longint;
begin
fillchar(dis, sizeof(dis), 255); dis[s] := 0;
fillchar(judge, sizeof(judge), true);
now := s;
repeat
judge[now] := false;
for i := 1 to n do if a[now, i] > 0 then
if (dis[now] + a[now, i] < dis[i])="" or="" (dis[i]="">< 0)="" then="" dis[i]="" :="dis[now]" +="" a[now,="" i];="" now="" :="s;" for="" i="" :="1" to="" n="" do="" if="" (dis[i]=""> 0) and (judge[i]) then
if (dis[i] < dis[now])="" or="" (now="s)" then="" now="" :="i;" until="" (now="t)" or="" (now="s);" end;="" procedure="" print;="" begin="" writeln(dis[t]);="" end;="" begin="" assignfile;="" init;="" process;="" print;="" closefile;="">

---

　　分给我，这是模板，很好用，我做acm用的

#define MAX 110
#define MAXVALUE 1000

int Cost[MAX][MAX],Dist[MAX];

void Dijkstra(int n,int v,int *Dist) //或 int Dist[MAX];
{
int newdist,i,j,temp,u;
bool s[MAX];

for(i=0;i

---

　　spfa在稀疏图上快，因为是通过边来增广的。dijkstra在稠密图上快。因为是通过点来增广的。某些情况下dijkstra 加上堆优化，在处理大数据的时候会比spfa快很多；但是spfa在随机数据的综合表现中相比dijkstra优势还是比较大的。总而言之，各有所长。