Dijkstra：
裸的算法，O(n^2)，使用邻接矩阵：
算法思想：
定义两个集合，一开始集合1只有一个源点，集合2有剩下的点。
STEP1：在集合2中找一个到源点距离最近的顶点k：min{d[k]}
STEP2：把顶点k加入集合1中，同时修改集合2中的剩余顶点j的d[j]是否经过k之后变短，若变短则修改d[j];
if d[k]+a[k,j]<d[j] then d[j]=d[k]+a[k,j];
STEP3：重复STEP1，直到集合2为空为止。
#include <iostream>
#include <cstring>
using namespace std;
#define MAXINT 9999999 int minx,minj,x,y,t,k,n,m,tmp;
int v[],d[],a[][]; int main()
{
cin>>n>>m>>k;
memset(a,,sizeof(a));
memset(d,MAXINT,sizeof(d));
memset(v,,sizeof(v));
d[k]=;
for (int i=;i<=m;i++)
{
cin>>x>>y>>t;
a[x][y]=t;
a[y][x]=t;
} for (int i=;i<=n-;i++)
{
minx=MAXINT;
for (int j=;j<=n;j++)
if ((v[j]==)&&(d[j]<minx))
{
minx=d[j];
minj=j;
}
v[minj]=;
for (int j=;j<=n;j++)
if ((v[j]==)&&(a[minj][j]>))
{
tmp=d[minj]+a[minj][j];
if (tmp<d[j]) d[j]=tmp;
}
} for (int i=;i<=n;i++)
cout<<d[i]<<" ";
cout<<endl; return ;
}
Tips：上述STEP1可以用优先队列优化。
模版：
（使用邻接表，Reference：http://www.cnblogs.com/qijinbiao/archive/2012/10/04/2711780.html）
eg：邻接表
i：某条边的起点 eg[i][j].x：从点i出发的第j条边的终点 eg[i][j].d：这条边的距离
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int Ni = ;
const int INF = <<;
struct node{
int x,d;
node(){}
node(int a,int b){x=a;d=b;}
bool operator < (const node & a) const
{
if(d==a.d) return x<a.x;
else return d > a.d;
}
};
vector<node> eg[Ni];
int dis[Ni],n;
void Dijkstra(int s)
{
int i;
for(i=;i<=n;i++) dis[i]=INF;
dis[s]=;
priority_queue<node> q;
q.push(node(s,dis[s]));
while(!q.empty())
{
node x=q.top();q.pop();
for(i=;i<eg[x.x].size();i++)
{
node y=eg[x.x][i];
if(dis[y.x]>x.d+y.d)
{
dis[y.x]=x.d+y.d;
q.push(node(y.x,dis[y.x]));
}
}
}
}
int main()
{
int a,b,d,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++) eg[i].clear();
while(m--)
{
scanf("%d%d%d",&a,&b,&d);
eg[a].push_back(node(b,d));
eg[b].push_back(node(a,d));
}
Dijkstra(k); for (int i=;i<=n;i++)
printf("%d\n",dis[i]); return ;
}
STL优先队列Reference：http://www.cnblogs.com/wanghetao/archive/2012/05/22/2513514.html
SPFA：
即用队列优化过的Bellman-Ford
( Reference:http://blog.csdn.net/niushuai666/article/details/6791765 )
Pascal代码...
var q,d:array[..] of longint;
a:array[..,..] of longint;
visited:array[..] of boolean;
head,tail,s,n,dt,i,j:longint; begin
assign(input,'spfa.in');
reset(input); fillchar(d,sizeof(d), div );
fillchar(visited,sizeof(visited),false);
fillchar(a,sizeof(a),); readln(s);
d[s]:=;
readln(n);
for i:= to n do
for j:= to n do
begin
read(dt);
a[i,j]:=dt;
a[j,i]:=dt;
{ if dt<>0 then
begin
if i=s then d[j]:=dt;
if j=s then d[i]:=dt;
end;
}
end; head:=;
q[]:=s;
visited[s]:=true;
tail:=;
while head<tail do
begin
inc(head);
visited[q[head]]:=false;
for i:= to n do
begin
if (a[q[head],i]>) and (d[q[head]]+a[q[head],i]<d[i]) then
begin
d[i]:=d[q[head]]+a[q[head],i];
if not visited[i] then
begin
inc(tail);
q[tail]:=i;
visited[i]:=true;
end;
end;
end;
end; for i:= to n do
write(d[i],' ');
writeln; close(input);
end.
Floyd：
多源最短路
//path[i,j]：用来输出最短路径
//floyd
var path,d:array[..,..] of longint;
n,k,i,j,st,en,x,y,tmp:longint; procedure dfs(i,j:longint);
begin
if path[i,j]> then
begin
dfs(i,path[i,j]);
write(path[i,j],'->');
dfs(path[i,j],j);
end;
end; begin
assign(input,'floyd.in');
reset(input); fillchar(d,sizeof(d), div ); readln(n); for i:= to n do d[i,i]:=;
for i:= to n do
for j:= to n do
path[i,j]:=-; readln(st,en);
while not eof do
begin
readln(x,y,tmp);
d[x,y]:=tmp;
d[y,x]:=tmp;
path[x,y]:=;
path[y,x]:=;
end; for k:= to n do
for i:= to n do
for j:= to n do
begin
if d[i,k]+d[k,j]<d[i,j] then
begin
d[i,j]:=d[i,k]+d[k,j];
path[i,j]:=k;
end;
end; writeln(d[st,en]); write(st,'->');
dfs(st,en);
writeln(en); close(input);
end.