[Algotithm] 最短路之旅

这可能是非常久以前的东西。

不过想想复习一下也是好的（其实是发现居然不会dijkstra了）。

一、通用原理

维护一个数组记录所有点的最短路。

枚举边确认是否可以通过这条边减小其它点的最短距离。

得出答案。

二、主流算法

　　A. Dijkstra

　　　　Dijkstra，荷兰人。

　　　　Dijkstra要求提供两个点集，分别用于存放不再修改的点与待修改的点（也就是是否找到最短路）

　　　　显然第一个不再修改的点是起点，且其最短路为0。

　　　　那么，首先找到已知的最短路径最短的点（想象一个凸多边形，哪里离中心最近就哪里进行扩张）。

　　　　然后这个点扔进不再修改的点集（记为A）。

　　　　然后枚举其边以更新其它点的最短路。

　　　　显然，这种方式将持续n次，因为每次都必然扔且只扔一个点进去点集A。

　　　　然后查找的过程又是n次。

　　　　最后枚举边如果用邻接矩阵的话也是n次，如果用邻接表的话可以E（E是边数）。

　　　　PS：我并不是说准确次数啊，n-1 接近 n 所以我直接说 n QwQ

　　　　那么朴素dijkstra的复杂度就是O(n^2+nE)，近似看作O(n^2)。

　　　　

　　　　堆优化：

　　　　　　想要减小时间复杂度，第一个要优化的就是查找枚举基点的过程，毕竟每次都O(n)。

　　　　　　这段部分就其根本是要找到可修改的最短距离。

　　　　　　那么我们可以用一个堆（或优先队列）代替原来的朴素队列使得我们要找的最小dis每次就在堆顶。

　　　　　　

　　　　题目：

　　　　　　单源最短路：https://www.luogu.org/problem/show?pid=3371

　　　　　　这道题数据还算不错。

　　　　　　注意：数据大小需要注意。

#include<cstdio>
#include<iostream>
#include<queue>
#define maxn_P 10101
#define maxn_E 505050
#define INF 2147483647
using namespace std;
typedef pair<int,int> node;

struct edge{
    int from,v,len;
}e[maxn_E];

int first[maxn_P],tot,dis[maxn_P],n,m,s,a,b,c;
bool book[maxn_P];

void insert(int u,int v,int len){
    tot++;
    e[tot].from = first[u];
    e[tot].v = v;
    e[tot].len = len;
    first[u] = tot;
}

void dijkstra(){
    for(int i = 1;i <= n;i++) dis[i] = INF;
    
    priority_queue<node,vector<node>,greater<node> > q;
    
    dis[s] = 0;
    
    q.push(make_pair(dis[s],s));
    
    while(!q.empty()){
        node tmp = q.top();
        q.pop();
        int p = tmp.second;
        
        if(!book[p]){
            book[p] = true;
            for(int i = first[p];i;i = e[i].from){
                if(dis[e[i].v] > dis[p]+e[i].len){
                    dis[e[i].v] = dis[p]+e[i].len;
                    q.push(make_pair(dis[e[i].v],e[i].v));
                }
            }
        }
    } 
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    
    for(int i = 0;i < m;i++){
        scanf("%d%d%d",&a,&b,&c);
        insert(a,b,c);
    }
    
    dijkstra();
    
    for(int i = 1;i <= n;i++){
        printf("%d ",dis[i]);
    }
    
    return 0;
}

　　　　　　　　

To be filled