一：迪杰斯特拉(Dijkstra)算法
Dijkstra算法是单源最短路算法。他能求出一个点到其他点的最短距离。这个点叫做源点；
他的主要思路就是将所有顶点分为两部分，一部分是点集合是Q,剩下部分点集合是P;其中Q集合的点到源点的最短距离
已经求出来，P集合是待求到源点最短距离的点集合；
Dijkstra就是对这两个集合进行操作。
我们假定源点是S.
第一步:我们将两个集合初始化，Q集合只有S点，P集合是除S点剩下的点。因为S点到S点的最短距离已经确定，是0；
第二步：在P集合选取出一个距离S点最近的一个点，然后通过这个点对S点和其他点进行松弛；
第三步：重复第二步，直到这个过程进行了n-1次；
代码如下(复杂度为n^2)：
#include<stdio.h>
#include<string.h>
#define mmset(a,b) memset(a,b,sizeof(a))
const int N = 1005;
const int INF = 1e9;
int book[N] ; //用来标记该点是在Q集合还是P集合。
int dis[N]; //用来储存源点到其他点的最短距离
int map[N][N] ; //邻接矩阵的存图方式；
/*
4 8 1
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
*/
int main()
{
int n,m,s;
scanf("%d %d %d",&n, &m, &s);
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j)
map[i][j] = 0;
else
map[i][j] = INF;
}
}
for(int i = 1; i <= m; i++)
{
int x,y,c;
scanf("%d %d %d",&x,&y, &c);
map[x][y] = c; // 假定输入的是一个有向图；
}
}
for(int i = 1; i <= n; i++)
dis[i] = map[s][i];
dis[s] = 0, book[s] = 1;
for(int i = 1; i <= n-1; i++)
{
int min = INF, u = 0;
for(int j = 1; j <= n; j++) if(book[j] == 0 && dis[j] < min)
{
min = dis[j]; //P集合选取出一个距离S点最近的一个点
u = j;
}
book[u] = 1;
for(int v = 1; v <= n; v++) if(dis[v] > dis[u] + map[u][v] && map[u][v] < INF)
{
dis[v] = dis[u] + map[u][v]; //通过u点对S点和其他点进行松弛
}
}
for(int i = 1; i <= n; i++)
{
printf("%d ",dis[i]);
}
printf("\n");
return 0;
}
Dijkstra算法在选取离S点最近的一个点的时候可以用优先队列优化，代码如下(复杂度为n*Log(n) )：
#include<stdio.h>
#include<string.h>
#include<queue>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 1005;
int INF = 1e9;
struct node //优先队列的元素，num代表该点，w表示s到点num的距离
{
int num,w;
bool operator < (const node b) const //重载<
{
return w > b.w;
}
};
int n,m,s;
int map[N][N],dis[N];
int main()
{
mmset(map,54);
INF = map[0][0];
scanf("%d %d %d",&n,&m,&s);
for(int i = 1; i <= m; i++)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
map[x][y] = c;
}
priority_queue <node> que;
for(int i = 1; i <= n; i++) if(i != s)
{
dis[i] = map[s][i];
node temp ;
temp.num = i, temp.w = dis[i];
que.push(temp);
}
dis[s] = 0;
for(int i = 1; i <= n - 1; i++)
{
node p = que.top();
que.pop();
int u = p.num;
for(int v = 1; v <= n; v++) if(dis[v] > dis[u] + map[u][v] && map[u][v] < INF)
{
dis[v] = dis[u] + map[u][v];
node temp;
temp.num = v, temp.w = dis[v];
que.push(temp);
}
}
for(int i = 1; i <= n; i++)
{
printf("%d ",dis[i]);
}
printf("\n");
return 0;
} 迪杰斯特拉队列优化 + 打印路径：
#include<stdio.h>
#include<string.h>
#include<queue>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 1005;
int INF = 1e9;
struct node //优先队列的元素，num代表该点，w表示s到点num的距离
{
int num,w;
bool operator < (const node b) const //重载<
{
return w > b.w;
}
};
int n,m,s;
int map[N][N],dis[N], path[N]; //path记录路径
void printfPath(int p);
int main()
{
mmset(map,54);
mmset(path,-1) ;
INF = map[0][0];
scanf("%d %d %d",&n,&m,&s);
for(int i = 1; i <= m; i++)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
map[x][y] = c;
}
priority_queue <node> que;
for(int i = 1; i <= n; i++) if(i != s)
{
dis[i] = map[s][i];
node temp ;
temp.num = i, temp.w = dis[i];
que.push(temp);
}
dis[s] = 0;
for(int i = 1; i <= n - 1; i++)
{
node p = que.top();
que.pop();
int u = p.num;
for(int v = 1; v <= n; v++) if(dis[v] > dis[u] + map[u][v] && map[u][v] < INF)
{
path[v] = u; //s到v点可以通过u点松弛，说明s到v点一定经过u点
dis[v] = dis[u] + map[u][v];
node temp;
temp.num = v, temp.w = dis[v];
que.push(temp);
}
}
for(int i = 1; i <= n; i++)
{
printf("%d ",dis[i]);
}
printf("\n");
for(int i = 1; i <= n; i++)
{
printfPath(i); //输出源点到i点的路径
printf("\n");
}
return 0;
}
void printfPath(int p)
{
if(p == -1)
{
printf("%d ",s);
return ;
}
else
{
printfPath(path[p]);
printf("%d ",p);
}
}
二.Spfa算法：
Spfa算法同Dijkstra一样，也是求单源最短路的算法；
他的主要算法分为以下几步；
第一步：将源点S加入队列。
第二步：将队列的队首弹出来，假设队首点为now,now连接的点为Pj。通过now松弛S点和Pj。
如果能松弛就更新S点到Pj的距离。如果Pj没在队列中，就把他加入队列中。
第三步：重复第二步，知道队列为空；
代码如下(复杂度为n*m)
#include<stdio.h>
#include<string.h>
#include<queue>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 1005;
int INF = 1e9;
struct node
{
int to,w,next;
};
node edges[N*N];
int head[N], dis[N], book[N];
int n,m,s ,index = 1;
void addEdge(int x,int y,int c)
{
edges[index].to = y,edges[index].w = c;
edges[index].next = head[x];
head[x] = index;
index++;
}
int main()
{
scanf("%d %d %d",&n,&m,&s);
mmset(head,-1);
mmset(book,0);
mmset(dis,54);
INF = dis[0];
index = 1;
for(int i = 1; i <= m; i++)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
addEdge(x,y,c); //链式前向星建图
}
dis[s] = 0; //初始化dis数组，注意这与Dijkstra不一样
queue <int> que;
que.push(s);
while(!que.empty())
{
int now = que.front();
book[now] = 0;
que.pop();
for(int i = head[now]; i != -1; i = edges[i].next)
{
int to = edges[i].to;
int w = edges[i].w;
if(dis[to] > dis[now] + w)
{
dis[to] = dis[now] + w;
if(book[to] == 0) //判断to点是否在队列中
{
que.push(to);
book[to] = 1;
}
}
}
}
for(int i = 1; i <= n; i++)
{
printf("%d ",dis[i]);
}
printf("\n");
return 0;
}
spfa + 打印路径
#include<stdio.h>
#include<string.h>
#include<queue>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 1005;
int INF = 9999999;
struct node
{
int to,w,next;
};
node edges[N*N];
int head[N], path[N],dis[N],book[N]; //path记录路径
int n,m,s,index = 1;
void addEdge(int x,int y,int c)
{
edges[index].to = y, edges[index].w = c;
edges[index].next = head[x];
head[x] = index++;
}
void printfPath(int p);
int main()
{
scanf("%d %d %d",&n,&m,&s);
index = 1;
mmset(head,-1);
for(int i = 1; i <= m; i++)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
addEdge(x,y,c);
}
mmset(dis,54);
INF = dis[0];
dis[s] = 0;
queue <int> que;
que.push(s);
while(!que.empty())
{
int now = que.front();
que.pop();
book[now] = 0;
for(int i = head[now]; i != -1; i = edges[i].next)
{
int to = edges[i].to;
int w = edges[i].w;
if(dis[to] > dis[now] + w)
{
path[to] = now;
dis[to] = dis[now] + w;
if(book[to] == 0)
{
book[to] = 1;
que.push(to);
}
}
}
}
for(int i = 1; i <= n; i++)
{
printf("%d ",dis[i]) ; //输出源点到i点的最短路的长度
}
printf("\n");
for(int i = 1; i <= n; i++)
{
printfPath(i); //输出源点到i点的路径
printf("\n");
}
return 0;
}
void printfPath(int p)
{
/*
这点值得注意，因为最先开始从源点松弛 ，所以找的源点就开始往回回溯。
在迪杰斯特拉中，因为初始化dis时，就把源点到i点的距离已经给初始化了。所以源点并没有参与
松弛。随意在迪杰斯特拉中回溯到最开始的时候(也就是path==-1)时开始往后回溯。
*/
if(p == s)
{
printf("%d ",s);
return ;
}
else
{
printfPath(path[p]);
printf("%d ",p);
}
} 总结一下：
Djikstra适用于稠密图，Spfa适用于稀疏图
京公网安备 11010502036488号