沐晴の编程blog

首先对于图的储存，邻接矩阵（稀疏图），邻接表，链式前向星，三种储存方法本质是存的相同的信息，我最开始接触的最短路是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 &gt; dis[mask][u]) continue;

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

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

        // 到达v后，合并v的状态（拾取钥匙）
        int next_mask = mask | key[v];
        if (dis[next_mask][v] &gt; 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 &amp;e:g[u]){
        int v=e.v;
        ll w=e.w;
        if(dis[v] &gt; dis[u] + w){
            dis[v] = dis[u]+w;
            if(!inq[v]){
                q.push(v);
                inq[v]=true;
                cnt[v]++;
                if(cnt[v]&gt;=n){
                    return false; //存在负环，从s可达
                }
            }
        }
    }
}
return true;

}

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