最短路径の算法 - 洛谷保存站

> **最短路**，未免对我这个蒟蒻来说太难了

这篇文章就梳理一下最短路径算法，**let's go**

## Part1：总体梳理

**chart**

**tips**:  
所有の最短路问题都不应存在负环，有了负环，就可以多转几圈来使最小值无限减小，至于你说**dijkstra**会有标记避免重复处理，但对于一个连负权边都无法出现的算法，ta能有负环吗？

## Part2：Floyd算法

蒟蒻本蒻认为这是最简单的算法了。

**思路：**  
dp思想  
设$dp_{i,j}$为点$i$到点$j$的最短路径长度，则引入一个断点$k$，$i$到$j$の路径长度为$i$到$k$的路径长度加上$k$到$j$的路径长度。

转移方程： 
$$dp_{i,j} = min(dp_{i,k}+dp_{k,j})$$

---
**实现细节：**  
一定先遍历$k$，再遍历$i,j$  
记得初始化dp数组为很大的值  
存图不用单独开邻接矩阵，可以直接存进dp数组

---
**code：**
```cpp
void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
		
}
```

## Part3：dijkstra

这个算法时间复杂度优秀，也比**SPFA**稳定。

**思路：**  
贪心+BFS思想

引入$dis$数组，$dis_i$表示$i$距离起点的最短距离。  
引入$vis$数组，$vis_i$表示$i$是否已经找到最短路。

- 从所有未访问节点中，选择当前 $dis$ 最小的节点 $u$（这一步体现贪心思想：因为边权非负，此时 $u$ 的最短路径已确定，不会再被其他路径更新）。

- 将 $u$ 加入“已访问节点” 集合，然后以 $u$ 为断点（类似于**Floyd**里那个$k$），遍历其所有邻接节点 $v$：若从起点通过 $u$ 到达 $v$ 的路径（即$dis_u$  + 边权$(u→v)$）比当前 $dis_v$ 更短，则更新 $$dis_v    =  dis_u + 边权(u→v)$$，这个就叫**松弛操作（relax）**。

- 重复步骤 2，直到所有节点都被加入 “已访问节点” 集合，此时 $dis$ 数组中存储的就是起点到各节点的最短路径。

---

**实现细节：**  
**dijkstra**の存储使用邻接表（对于每个点都用一个`vector`存储ta能到的点以及边权，边权与点可以使用`pair`存）  
寻找$dis$最小的点可以使用优先队列动态维护，但需注意：  
1. `priority_queue<数据类型>`默认大顶堆，我们需要重载ta为`priority_queue<数据类型,vector<数据类型>,greater<数据类型> >`变成小顶堆。
2. `pair`的比较是先比较`first`，再比较`second`，如果你不想手写结构体然后重载的话，就先存边权，再存点。
 
松弛操作那一块有可能会傻傻分不清，没事，多敲几次+理解记忆

---

**code：**
```cpp
typedef pair<int,int> pii;//f,v

vector<pii> graph[50005];

int dis[50005];
bool vis[50005];
priority_queue<pii,vector<pii>,greater<pii> > q;
	
void dijkstra(int st)
{
	
	for(int i=1;i<=n;i++)
	{
		vis[i] = false;
		dis[i] = INT_MAX;
	}
	
	dis[st]=0;
	q.push(make_pair(0,st));
	
	while(!q.empty())
	{
		pii u = q.top();
		q.pop();
		
		if(vis[u.second]) continue;
		vis[u.second] = true;
		
		for(int i=0;i<graph[u.second].size();i++)
		{
			pii uu = graph[u.second][i];
			if(dis[uu.second] > dis[u.second] + uu.first)
			{
				dis[uu.second] = dis[u.second] + uu.first;
				q.push(make_pair(dis[uu.second],uu.second));
			}
		}
	}
	
}

```

## Part4：SPFA
**SPFA**是**Bellman-Ford**算法的优化，此处不叙述**Bellman-Ford**算法，感兴趣の可以看[这里](https://blog.csdn.net/lsy201009/article/details/129149905)（推荐这篇好文），ta不是很常用。

**思路：**  
设立一个队列用来保存待松弛的顶点，每次取出队首顶点 $u$，并且用 $u$ 点当前的最短路径值 $dis_u$ 对与 $u$ 点邻接的顶点 $v$ 进行松弛操作，如果 $v$ 点的最短路径值 $dis_v$ 可以更小，且 $v$ 点不在当前的队列中，就将 $v$ 点放入队尾。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。（松弛操作：见**dijkstra**）  
而其检测负权回路的方法也很简单，如果某个点进入队列的次数大于等于 $n$，则存在负权回路，其中 $n$ 为图的顶点数。

---
**code：**
```cpp
// 起点s，节点总数n，返回是否有负环
bool spfa(int s, int n) {
    memset(d, 0x3f, sizeof(d));
    memset(cnt, 0, sizeof(cnt));
    memset(inq, 0, sizeof(inq));
    
    queue<int> q;
    d[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.to;
            int w = e.w;
            
            // 松弛操作
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    if (++cnt[v] >= n) {
                        return true;  // 存在负环
                    }
                }
            }
        }
    }
    return false;  // 无负环
}
```
--- 
#### that's all ， thanks！

正在渲染内容...