Dijkstra算法及优化
Dijkstra算法策略为：
设置集合s存放已被访问的顶点，然后执⾏n次下⾯两个步骤（n为顶点数）：
1. 每次从集合v-s中选择与起点s的最短路径最⼩的⼀个顶点，访问并加⼊集合s中
2. 之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短路径具体实现如下：
其中DFS函数⽤于输出访问的最短路径，其算法与DFS算法⼀致。
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXV=510;  //最⼤顶点数
const int INF=1000000;  //⽆穷⼤
struct Node{
int v;
int dis;  //v为边的⽬标顶点，dis为边权
};
int n,m,st,ed;  //n为顶点数，图G使⽤邻接表实现 ,st和ed分别为起点和终点
int d[MAXV],minCost=INF;  //起点到达⾃⾝的距离为0
int cost[MAXV][MAXV],G[MAXV][MAXV];
vector<int> pre[MAXV];  //前驱
vector<int> tempPath,path;  //临时路径，最优路径
bool vis[MAXV]={false};
void Dijkstra(int s){
fill(d,d+MAXV,INF);  //fill函数将整个d数组赋为INF
d[s]=0;  //u使d[u]最⼩，min存放该最⼩的d[u]
for(int i=0;i<n;i++){  //循环n次
int u=-1,MIN=INF;  //u使d[u]最⼩，min存放该最⼩的d[u]
for(int j=0;j<n;j++){ //到未访问的顶点中d[]最⼩的
if(vis[j]==false&&d[j]<MIN){
u=j;
MIN=d[j];
}
}
//不到⼩于INF的d[u]，说明剩下的顶点和起点s不连通
if(u==-1)
return ;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
//如果v未访问&&u能到达v
if(d[u]+G[u][v]<d[v]){
//如果v未访问并且以u为中介点可以使d[v]更优
d[v]=d[u]+G[u][v]; //优化d[v]
pre[v].clear();  //清空pre[v]
pre[v].push_back(u); //u为v的前驱
}
else if(d[u]+G[u][v]==d[v]){  //到相同长度的路径
pre[v].push_back(u); //u为v的前驱之⼀
}
}
}
}
}
void DFS(int v){  //v为当前结点
if(v==st){  //v为起点编号，s为当前访问的顶点编号
tempPath.push_back(v);
int tempCost=0;  //记录当前路径的花费之和
for(int i=tempPath.size()-1;i>0;i--){  //倒着访问
//当前结点id，下个结点idnext
int id=tempPath[i],idNext=tempPath[i-1];
tempCost+=cost[id][idNext];  //增加边id->idNext的边权
}
if(tempCost<minCost){  //如果当前路径的边权之和更⼩
minCost=tempCost;  //更新minCost
path=tempPath;  //更新path
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i=0;i<pre[v].size();i++){
DFS(pre[v][i]);  //递归访问v的前驱结点pre[v]
}
tempPath.pop_back();
}
int main(){
scanf("%d%d%d%d",&n,&m,&st,&ed);
int u,v;
fill(G[0],G[0]+MAXV*MAXV,INF);  //初始化G
fill(cost[0],cost[0]+MAXV*MAXV,INF);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
scanf("%d%d",&G[u][v],&cost[u][v]);
G[v][u]=G[u][v];
cost[v][u]=G[u][v];
}
Dijkstra(st);  //算法⼊⼝
DFS(ed);  //获取最佳路径
for(int i=path.size()-1;i>=0;i--){
printf("%d ",path[i]);  //倒着输出路径上的结点
}
printf("%d %d\n",d[ed],minCost);  //最短距离，最短路径上的花费
return 0;
}
从复杂度来看，主要是外层循环O(n)与内层循环寻最⼩的d[u]需要O(n)，枚举v需要O(adj[u].size)产⽣的。对于整个程序来说，时间复杂度为O((n^2+m)).
优化算法:
寻最⼩的d[u]不必达到O(n)的复杂度，⽽可以使⽤堆优化来降低复杂度。直接使⽤STL中的优先队列，这样使⽤邻接表实现的Dijkstra算法的时间复杂度可以降为O(n*logn+m).
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXV=510;  //最⼤顶点数
const int INF=1000000;  //⽆穷⼤
struct Node{
int v;
int dis;  //v为边的⽬标顶点，dis为边权
friend bool operator <(Node f1,Node f2){ //默认从⼤到⼩输出，所以反向重载
return f1.dis>f2.dis;
}
};
int n,m,st,ed;  //n为顶点数，图G使⽤邻接表实现 ,st和ed分别为起点和终点
int d[MAXV],minCost=INF;  //起点到达⾃⾝的距离为0
int cost[MAXV][MAXV],G[MAXV][MAXV];
int cost[MAXV][MAXV],G[MAXV][MAXV];
vector<int> pre[MAXV];  //前驱
vector<int> tempPath,path;  //临时路径，最优路径
bool vis[MAXV]={false};
priority_queue<Node> q;
void Dijkstra(int s){
fill(d,d+MAXV,INF);  //fill函数将整个d数组赋为INF
d[s]=0;
q.push({s,0});  //u使d[u]最⼩，min存放该最⼩的d[u]
for(int i=0;i<n;i++){  //循环n次
int u=-1,MIN=INF;  //u使d[u]最⼩，min存放该最⼩的d[u]  p().v;  //堆优化
q.pop();
//不到⼩于INF的d[u]，说明剩下的顶点和起点s不连通  if(u==-1)
return ;
cstring转为intvis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
//如果v未访问&&u能到达v
if(d[u]+G[u][v]<d[v]){
//如果v未访问并且以u为中介点可以使d[v]更优
d[v]=d[u]+G[u][v]; //优化d[v]
q.push({v,d[v]});
pre[v].clear();  //清空pre[v]
pre[v].push_back(u); //u为v的前驱
}
else if(d[u]+G[u][v]==d[v]){  //到相同长度的路径
pre[v].push_back(u); //u为v的前驱之⼀
}
}
}
}
}
void DFS(int v){  //v为当前结点
if(v==st){  //v为起点编号，s为当前访问的顶点编号
tempPath.push_back(v);
int tempCost=0;  //记录当前路径的花费之和
for(int i=tempPath.size()-1;i>0;i--){  //倒着访问
/
/当前结点id，下个结点idnext
int id=tempPath[i],idNext=tempPath[i-1];
tempCost+=cost[id][idNext];  //增加边id->idNext的边权  }
if(tempCost<minCost){  //如果当前路径的边权之和更⼩  minCost=tempCost;  //更新minCost
path=tempPath;  //更新path
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i=0;i<pre[v].size();i++){
DFS(pre[v][i]);  //递归访问v的前驱结点pre[v]
}
tempPath.pop_back();
}
int main(){
scanf("%d%d%d%d",&n,&m,&st,&ed);
int u,v;
fill(G[0],G[0]+MAXV*MAXV,INF);  //初始化G
fill(cost[0],cost[0]+MAXV*MAXV,INF);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
scanf("%d%d",&G[u][v],&cost[u][v]);
G[v][u]=G[u][v];
cost[v][u]=G[u][v];
cost[v][u]=G[u][v];
}
Dijkstra(st);  //算法⼊⼝
DFS(ed);  //获取最佳路径
for(int i=path.size()-1;i>=0;i--){
printf("%d ",path[i]);  //倒着输出路径上的结点
}
printf("%d %d\n",d[ed],minCost);  //最短距离，最短路径上的花费 return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。