Dijkstra算法
朴素的Dijkstra算法和prim算法在代码上惊人的相似。
而Dijkstra算法的思想是:在待扩展边中取出最小边,利用此边进行松弛操作,然后更新待扩展边集。重复以上步骤直到所有结点都已访问过。
Dijkstra算法只对没有负权回路的图有效,当然对带负权边,但没有负权回路的图依然有效。
for (int i=1;i<n;i++)
{
minn=INF;
for (int j=1;j<=n;j++)
if (!vis[j] && d[j]<minn)
minn=d[k=j];
vis[k]=true;
for (int j=1;j<=n;j++)
d[j]=min(d[j],d[k]+map[k][j]);
}
明显朴素的Dijkstra算法耗时O(N^2),时间主要浪费在每次循环寻找待扩展边中的最小边,利用C++的STL提供的方便,使用优先队列进行优化,当然图的存储方法只能改为使用边表存储,否则松弛操作一样耗时巨大。下面的代码写得一般,有点长了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
struct edge{ //存储边
int v,w;
edge() { v=w=0; }
edge(int x,int y) { v=x; w=y; }
};
vector<edge> a[100];
struct node{ //存储待扩展边的数据,当然也可以直接利用存储边的结构体,但是为了直观就分开写了
int dd,w; //dd存储结点,w存储边权
node() {dd=w=0; };
node(int x,int y) { dd=x;w=y; }
bool operator < (const node &x) const //优先队列比较函数
{
if (w==x.w) return dd<x.dd;
else return w<x.w;
}
};
int d[100];
int dis[100];
void dijkstra(int S)
{
priority_queue<node> p;
memset(dis,10,sizeof(dis));
dis[S]=0;
p.push(node(S,dis[S])); //把start点压入队列
while (!p.empty())
{
node u=p.top(); p.pop(); //弹出待扩展边的最小边
for (int i=0;i<d[u.dd];i++) //松弛操作
{
edge e=a[u.dd][i];
if (dis[e.v]>u.w+e.w)
{
dis[e.v]=u.w+e.w;
p.push(node(e.v,dis[e.v])); //待扩展边进队
}
}
}
}
int main()
{
for (int i=0;i<100;i++) a[i].clear();
memset(d,0,sizeof(d));
int n,m,u,v,w;
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>u>>v>>w;
a[u].push_back(edge(v,w));
d[u]++;
}
dijkstra(1);
for (int i=1;i<=n;i++)
cout<<"1->"<<i<<":"<<dis[i]<<endl;
return 0;
}
Bellman-Ford算法
朴素的bellman-ford算法说死了就是一个笨方法,就是通过不断地对每一条边进行松弛操作,耗时O(VE),但是经过一个简单的优化后效率大大提升,听说效率比Dijkstra好多了。
这里直接给出经过优化的bellman-ford算法。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NN 105
struct edge{
int u,v,w;
edge() {u=v=w=0;}
edge(int x,int y,int z) {u=x;v=y;w=z;}
};
vector <edge> e;
int n;
int dis[NN];
bool relax(int u,int v,int w) //松弛操作
{
if (dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
return true;
}
return false;
}
bool Bell(int S)
{
memset(dis,10,sizeof(dis));
dis[S]=0;
bool flag=false;
int count=0;
while (!flag && ++count<n) //注意flag的变化,其实flag就是优化,不用flag则运行n-1次也会停下来
{
for (int i=0;i<e.size();i++)
flag=flag||relax(e[i].u,e[i].v,e[i].w); //如果没有进行过松弛操作,那么就没必要在做下去了
flag=!flag;
}
for (int i=0;i<e.size();i++) //负权回路的判断
if (relax(e[i].u,e[i].v,e[i].w))
return false;
return true;
}
int main()
{
int m,u,v,w;
cin>>n>>m;
e.clear();
for (int i=1;i<=m;i++)
{
cin>>u>>v>>w;
e.push_back(edge(u,v,w));
e.push_back(edge(v,u,w));
}
bool ff=Bell(1);
if (!ff)
cout<<"no"<<endl;
else for (int i=2;i<=n;i++)
cout<<dis[i]<<endl;
return 0;
}
SPFA算法
SPFA算法是西南交大段凡丁发表的,在bellman-ford的基础上加入了队列优化,而在SPFA算法上又可以加入SLF和LLL优化,使得整个算法的效率非常可观。
算法的思想是从队列中取出点进行松弛操作,若松弛成功则加入队列,直到队列为空。而为了处理负权回路,需要加入一个数组记录结点入队的次数,若一个结点入队次数大于n,则可以判断出现了负权回路。
这里并没有加入SLF和LLL优化。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define NN 1000
struct edge{
int v,w;
edge() {v=w=0;}
edge(int x,int y) {v=x;w=y;}
};
vector<edge> e[NN];
int dis[NN];
int n;
bool relax(int u,int v,int w) //松弛操作
{
if (dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
return true;
}
return false;
}
bool SPFA(int S)
{
memset(dis,10,sizeof(dis));
dis[S]=0;
int count[NN]={0}; //统计入队次数
count[S]=1;
queue<int> q;
q.push(S);
bool f[NN]={0}; //标记是否在队列中,避免重复进队
f[S]=true;
while (!q.empty())
{
int u=q.front();
for (int i=0;i<e[u].size();i++)
{
int v=e[u][i].v;
if (count[v]>=n) return false;
if (!f[v] && relax(u,v,e[u][i].w))
{
count[v]++;
q.push(v);
f[v]=true;
}
}
q.pop();
f[u]=false;
}
return true;
}
int main()
{
int m,u,v,w;
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>u>>v>>w;
e[u].push_back(edge(v,w));
e[v].push_back(edge(u,w)); //无向图
}
bool ff=SPFA(1);
if (!ff) cout<<"no"<<endl;
else for (int i=2;i<=n;i++)
cout<<dis[i]<<endl;
return 0;
}
Floyd算法
Floyd算法最简单但是速度不敢恭维。
思想:对每个节点不断进行松弛操作,到最后得到的结果就是多源最短路的结果了。
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
原文链接: https://www.cnblogs.com/ay27/archive/2012/12/10/2811821.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/72134
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!