还是markdown好用,会HTML就能搞点 好 东西
最近发现伪码是个好东西。
<好>啊
单源最短路
Dijkstra算法
(荷兰人名字多少带点怪(滑稽))
算法思想
在我看来,是在只关心路的长度的情况下,找没有用过的最短边去凑。是一种贪心。
具体说:
从一个点出发到图中任何一个点,每两点之间的距离最多只需要检查一次就足够计算出最短路了。
1.设起点到每个点的距离为无穷大
2.找到最小的边,更新起点到这个点的距离
重复2直到检查过所有的边为止。
3.输出到目标点的距离
伪码
点击查看代码
初始化vis(设为否)和d数组(d[起点]=0,d[别的]=INF)
(vis判断是否被访问过,d[i]记录起点到i的距离)
循环n次{
在所有未vis过的边里,选出d最小的点x
给x标记
对于从x出发的所有边,更新:
d[y]=min{d[y],d[x]+w(x->y)
}
优化
看到这,我知道:最麻烦的事情变成如何找到最短的没被访问过的边?
优先队列出马。
接下来还想问:怎么存图?
随便。
不过我喜欢链式前向星
代码实现
#include<iostream>
#include<queue>
#define maxn 1005
#define INF 1000000000
using namespace std;
struct edge{
int next;
int to;
int v;
}e[maxn];
struct node{
int d;
int x;
bool operator <(const node &a)const{
return d>a.d;
}
};
priority_queue<node> q;
int head[maxn],vis[maxn],d[maxn],n,m,s,cnt;
void add(int x,int y,int w){
e[++cnt].to=y;
e[cnt].v=w;
e[cnt].next=head[x];
head[x]=cnt;
}
void Dijkstra(){
for(int i=1;i<=maxn;i++) vis[i]=0,d[i]=INF;
d[s]=0;
q.push((node){0,s});
while(!q.empty()){
node tmp=q.top();q.pop();
int x=tmp.x;
if(vis[x])continue;
vis[x]=true;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(d[y]>d[x]+e[i].v)
d[y]=d[x]+e[i].v;
if(!vis[y])
q.push((node){d[y],y});
}
}
}
(TBC)