首先对于图的储存，邻接矩阵（稀疏图），邻接表，链式前向星，三种储存方法本质是存的相同的信息，我最开始接触的最短路是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，dis变成二维的，，判断时，考虑不改变状态在本层遍历和改变状态换层遍历，一般用二进制表示状态，|是或运算，~是取反运算,^是异或，&是按位与
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去判断是否存在负环，同时也能求路径最值，不同于dijistra，spfa是依靠queue来实现的,对于差分约束，用spfa遍历的时候建立一条0连接所有点的0长度边，并用cnt数组计数，每次遍历子节点，都要累加，如果某个节点的cnt大于等于n，说明存在负环，然后以0作为起点搜索，注意，差分约束只能建立单向边，因为基于的不等式只有一个，判断建边的方式：把题给出的不等式转化成a<=b+k的形式，建立g[a].push_back({b,k})的形式
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，代码非常简洁，相比前面的逻辑都要清纯了很多，代码就不在这里做过多介绍了，读者感兴趣可以自己去搜索
补：bfs走迷宫的问题遇到了一种新的变种，01bfs,即边权是0或1，这个时候bfs就不能用原本的queue储存，普通的队列无法保持其有序性，所以要向双端队列的两端插入权值，保证内部元素的有序性(保证每次取出队首的一定是最小元素)，如果走0权边，将元素插到队头，否则插到队尾，且01bfs不需要vis数组，代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void solve()
{
int n,m,sx,sy,ex,ey;
cin>>n>>m;
vector<string>mp(n+1);
vector<vector<int>>dis(n+1,vector<int>(m+1,INF));
deque<pair<int,int>>dq;
for(int i=1;i<=n;i++) cin>>mp[i];
cin>>sx>>sy;
dis[sx][sy]=0;
dq.emplace_front(sx,sy);
while(!dq.empty())
{
auto [x,y] = dq.front();dq.pop_front();
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='#') continue;
int w = mp[nx][ny]=='1'?1:0;
if(dis[nx][ny]>dis[x][y]+w)
{
dis[nx][ny]=dis[x][y]+w;
w?dq.emplace_back(nx,ny):dq.emplace_front(nx,ny);
}
}
}
cout<<dis[ex][ey]<<endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;}