以下第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
26int 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
5int 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]);