首先对于图的储存，邻接矩阵（稀疏图），邻接表，链式前向星，三种储存方法本质是存的相同的信息，我最开始接触的最短路是dijistra算法，这里主要介绍它的堆优化版本：

void dijistra(int s){
    for(int i = 1;i <= n;i++) dis[i] = inf;
    dis[s] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.emplace(dis[s],s);
    while(!q.empty()){
        auto[d,u] = q.top(); q.pop();
        if(d > dis[u]) continue;
        for(auto [v,w]:g[u]){
            if(dis[v] > dis[u]+w){
                dis[v] = dis[u]+w;
                q.emplace(dis[v],v);
            }
        }
    }
}

‍

同时，作为图论里通用的dfs和bfs,同样也可以搜索图，但dfs递归很容易爆栈，在竞赛时，大多数时候使用广搜而不是深搜，bfs很适合求无权图的最短路，以及走迷宫类型的问题，dfs其实不止可以用在图里，它也可以作为数字全排列的模型，通过递归枚举每一个数字，如果被使用过就标记，如果不满足条件就回溯（即在递归之后执行和递归前相反的操作）

void dfs(int u)
{
    vis[u] = true;
    //此处写对u的处理逻辑
    for(int v : g[u])
    {
        if(!vis[v])
        {
            dfs(v);
        }
      }
}

void bfs(int st,int n)
 {
memset(dis,-1,sizeof dis);
     queue<int> q;
     dis[st]=0;
     q.push(st);
     while(!q.empty())
     {
         int u = q.front(); q.pop();
         for(int v : g[u])
         {
             if(dis[v]==-1)
             {
                 dis[v]=dis[u]+1;
                 q.push(v);
             }
         }
     }
 }

dijistra还有变式，如果对于每个点，存在状态mask,就需要状态压缩最短路来多层处理,核心思路是把节点编号+状态mask当作分层图的独立点，在分层图里跑dijistra

struct Edge {
    int v, w, need;         // 终点、边权、通行所需状态mask
};
vector<Edge> g[MAXN];

int key[MAXN];              // 每个点自带的状态（钥匙），按位或
int dis[MAX_MASK][MAXN];    // dis[mask][u]：到达u且状态为mask的最短路

// 小根堆：{距离, {节点, 状态mask}}
priority_queue<
    pair<int, pair<int, int>>,
    vector<pair<int, pair<int, int>>>,
    greater<pair<int, pair<int, int>>>
> q;

void dijkstra(int start) {
    memset(dis, 0x3f, sizeof dis);
    int init_mask = key[start];
    dis[init_mask][start] = 0;
    q.push(make_pair(0, make_pair(start, init_mask)));

    while (!q.empty()) {
        int d = q.top().first;
        int u = q.top().second.first;
        int mask = q.top().second.second;
        q.pop();

        if (d > dis[mask][u]) continue;

        for (size_t i = 0; i < g[u].size(); ++i) {
            int v = g[u][i].v;
            int w = g[u][i].w;
            int need = g[u][i].need;

            // 状态不满足通行条件，跳过
            if ((mask & need) != need) continue;

            // 到达v后，合并v的状态（拾取钥匙）
            int next_mask = mask | key[v];
            if (dis[next_mask][v] > d + w) {
                dis[next_mask][v] = d + w;
                q.push(make_pair(dis[next_mask][v], make_pair(v, next_mask)));
            }
        }
    }
}

bfs通过栈实现，压起点进栈，然后标记访问，然后不断取栈顶元素，先弹出，然后遍历该元素的邻边，如果没有访问过就加1，然后把相邻的点压入栈里，直到栈内元素被弹空，图遍历完整，对于迷宫，需要把邻接表换成邻接矩阵

如果存在负环，就不能用dijistra遍历图了，对于这种图，我们可以采用spfa去判断是否存在负环，同时也能求路径

struct Edge{
    int v; ll w;
};
vector<Edge> g[MAXN];
ll dis[MAXN];
bool inq[MAXN];   // 是否在队列中
int cnt[MAXN];    // 每个点入队次数，判负环
int n,m;

// s源点，返回true代表无负环；false代表存在可达负环
bool spfa(int s){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        inq[i]=false;
        cnt[i]=0;
    }
    queue<int> q;
    dis[s]=0;
    q.push(s);
    inq[s]=true;
    cnt[s]++;

    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=false;

        for(auto &e:g[u]){
            int v=e.v;
            ll w=e.w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u]+w;
                if(!inq[v]){
                    q.push(v);
                    inq[v]=true;
                    cnt[v]++;
                    if(cnt[v]>=n){
                        return false; //存在负环，从s可达
                    }
                }
            }
        }
    }
    return true;
}

如果要判断多个点的最短路，可以用floyd算法，我理解成就是一个三维dp，代码非常简洁，相比前面的逻辑都要清纯了很多，代码就不在这里做过多介绍了，读者感兴趣可以自己去搜索

沐晴

图上问题

一起同行的回忆

算法竞赛心路

夜间模式