最短路三大算法核心程序段

以下第1和第2均假设起点为1号点,终点为n号点。

Dijkstra

等待重写

SPFA

适用于单源最短路,可以处理负权边,不能处理负环。
思路:从起点开始寻找起点能到达的结点,然后按次序将结点入队,每当入队时标记入队,每当出队取消标记,重复处理,直到队列为空。
重点:和Dijkstra相比就是多了v数组用来保存结点是否在队列里,其结果导致同一个结点可以重复入队。而Dijkstra中所有结点都只能入队一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int e[1010][1010],ans[1010],v[1010],n;
//取e[a][b]=w表示存在一条从a通向b的道路,道路长度为w,其值应该在main中已经处理好
//取ans[i]表示从起点到结点i的距离为ans[i]
//取v[i]表示结点i是否在队列中
queue<int>q;
void spfa()
{
while(!q.empty()) q.pop();//清空队列
memset(v,0,sizeof(v));//初始化v数组
memset(ans,0,sizeof(ans));//初始化ans数组
q.push(1);//起点入队
v[1]=1;//起点标记为已经在队列中
while(!q.empty())//当队列非空时
{
int st=q.front();//取队头元素
q.pop();//弹出
v[st]=0;//标记队头元素为不在队列中
for(int i=1;i<=n;i++)//枚举所有点
{
if(i==1) continue;//如果i是起点,跳过
int p=0;//取变量p来记录是否发生更优解的更新
if(e[st][i]&&(!ans[i]||ans[i]>ans[st]+e[st][i])) ans[i]=ans[st]+e[st][i],p=1;//发生更优解的更新,p=1
if(p&&!v[i]) q.push(i),v[i]=1;//如果发生更优解的更新,且结点i未入队,则结点i入队,标记为已入队
}
}
}

Floyd

适用于求所有结点间的最短路径。

1
2
3
4
5
int d[100][100];//用d[i][j]表示从i到j的最短路径
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

--It's the end.Thanks for your read.--