【最短路】求最短路的几种算法(更新中)

还是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)

上一篇:如何在PHP中使用正则表达式找到完全匹配的内容?


下一篇:[CF1242B]0-1 MST 题解