简单地复习下最短路

· · 个人记录

最短路，比赛中最常用的就是迪杰斯特拉再加上亿一点点优化

实际上，所有最短路算法的基本思路就是绕近路：能找到一个点C，使得A→C→B的距离小于A→B，然后重复。

而这个C点怎么找，仁者见仁智者见智。你可以所有的点都找一遍:随便找三个点ABC，看看是否满足上面的规律，然后重复直到所有可能的点的组合都看过一遍。当然这是Floyd的思路，虽然有高达O(N^3）的复杂度，但它非常好写:

//P1529 [USACO2.4]回家 Bessie Come Home
#include <bits/stdc++.h>
using namespace std;
#define inf 114514
#define MAXN 55
int Map[MAXN][MAXN],int n;
int ctoI(char c){return c>96?c-70:c-64;}
char itoC(int c){return c>26?c+70:c+64;}

int main()
{
    for(int i=0;i<MAXN;i++){for(int j=0;j<MAXN;j++){Map[i][j]=inf;if(i==j){Map[i][j]=0;}}}
    cin>>n;
    for(int i=1,weight;i<=n;i++)
    {
        char a,b;
        cin>>a>>b>>weight;
        //cout<<ctoI(a)<<" "<<ctoI(b)<<endl;
        Map[ctoI(a)][ctoI(b)]=min(weight,Map[ctoI(a)][ctoI(b)]);
        Map[ctoI(b)][ctoI(a)]=min(weight,Map[ctoI(b)][ctoI(a)]);
    }
    for(int k=0;k<MAXN;k++)
    {
        for(int i=0;i<MAXN;i++)
        {
            for(int j=0;j<MAXN;j++)
            {
                Map[i][j]=min(Map[i][j],Map[k][j]+Map[i][k]);
            }
        }
    }
    int minC,minD=inf;
    for(int i=0;i<=25;i++)
    {
        if(minD>Map[i][26])
        {
            minD=Map[i][26];
            minC=i;
        }
    }
    cout<<itoC(minC)<<" "<<minD<<endl;
    return 0;
}

而迪杰斯特拉虽然有些复杂该死的邻接表什么鬼啊，但它的时间复杂度较低，优化后可达到O(E*logV)，其中E为边的数量，V为顶点的数量。

关于迪杰斯特拉的思路，就是维护一个集合一个数组。一个集合就是已找到最短路径的点的集合，数组就是代码里的dis数组。

下面就是一份迪杰斯特拉+堆优化+邻接表的模板：

#include <bits/stdc++.h>
using namespace std;
#define inf 2147483647
#define MAXL 200005
#define int long long

/*存图部分*/
struct EDGE
{
    int next, to, weight;
    //next:与这条边起点相同的上一条边的编号 
    //to:指向节点编号
    //weight:边权值 

} edge[MAXL];
int head[MAXL], cnt = 0;

void addEdge(int u, int v, int w)
{
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].weight = w;
    head[u] = cnt;
}

int n,m,s;//n:几个点   m:几条边  s:出发点 

/*堆优化部分*/
struct node
{
    int ans;//该点对应的dis值 
    int id;//该点对应的编号 
    bool operator<(const node &x)const
    {
        return x.ans<ans;
    }
};
priority_queue<node> q;

int dis[MAXL];
bool visited[MAXL];
void dijkstra2(int s)
{
    for (int j = 1; j <= n; j++)
    {
        dis[j]= inf;
        visited[j] = false;
    }
    dis[s] = 0;
    q.push((node){0,s});
    int pos=s;
    while(!q.empty())
    {
        node minP=q.top();
        q.pop();
        if(!visited[minP.id])
        {
            visited[minP.id]=1;
            for(int i=head[minP.id];i!=0;i=edge[i].next)
            {
                if(dis[minP.id]+edge[i].weight<dis[edge[i].to])
                {
                    dis[edge[i].to]=dis[minP.id]+edge[i].weight;
                    q.push((node){dis[edge[i].to],edge[i].to
                    });
                }
            }

        }
    }
}