图论中的经典问题：给一个图，求出起点到终点的最短路径。
Graph Representation
- adjacency matrix
| 0 | \(\infty\) | -1 | 4 | \(\infty\) | \(\infty\) |
| 1 | \(\infty\) | \(\infty\) | 3 | 2 | 2 |
| 2 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| 3 | \(\infty\) | 1 | 5 | \(\infty\) | \(\infty\) |
| 4 | \(\infty\) | \(\infty\) | \(\infty\) | -3 | \(\infty\) |
用vector<vector<int>> g(n, vector<int>(n, INF))表示，g[i][j]表示从顶点\(i\)到顶点\(j\)的权重，空间复杂度\(O(|V|^2)\)，适用于稠密图，用的不多；
- adjacency list
链表比较少用，基本都用动态数组：
| 1 | (2,3) | (3,2) | (4,2) | - | - |
| 2 | - | - | - | - | - |
| 3 | (1,1) | (2,5) | - | - | - |
| 4 | (3,-3) | - | - | - | - |
用vector<vector<pair<int, int>>> g表示，g[i][j].first表示从顶点\(i\)出发到达的顶点\(k\)，g[i][j].second表示从顶点\(i\)到顶点\(k\)的权值，空间复杂度\(O(|V|+|E|)\)。
edge list
(0,1,-1),(0,2,4),(1,2,3),(1,3,2),(1,4,2),(3,1,1),(3,2,5),(4,3,-3)
用vector<vector<int>> e表示，e[i][0]表示顶点\(u\)，e[i][1]表示顶点\(v\)，e[i][2]表示\(u\)到\(v\)的权值，空间复杂度\(O(|E|)\)。Dijkstra
单源最短路径算法，只能用于所有边权值为正的图，本质上还是贪心，思想：
- 将所有结点分为两类：已经确定最短路径的点集\(u\)、未确定最短路径的点\(v\)；
- 初始化\(dis[start]=0\)，其余结点\(dis\)设为无穷大；
- 找出一个\(dis\)最小的\(v\)中的点\(x\)，将其标记为\(u\)，遍历\(x\)的所有出边，若\(dis[y]>dis[x]+weight\)，则更新\(y\)点到源点的最短路径长度\(dis[y]=dis[x]+weight\)；
- 重复，直到所有点都在\(u\)中。
/*邻接矩阵版，适合顶点比较少的图，复杂度O(V^2)*/
int vertexNum, adjMatrix[MAXN][MAXN];
int dis[MAXN]; //起点到各点最短路径长度
bool visited[MAXN] = {false};
void Dijkstra(int start)
{
for (int i = 0; i < vertexNum; i++)
{
dis[i] = INFINITY;
}
dis[start] = 0;
for (int i = 0; i < vertexNum; i++)
{
//寻找未访问点中dis最小的
int u = -1, minDis = INFINITY;
for (int j = 0; j < vertexNum; j++)
{
if (visited[j] == false && dis[j] < minDis)
{
u = j;
minDis = dis[j];
}
}
if (u == -1) //剩余的点与起点不连通
return;
visited[u] = true;
//以u为中介试图优化dis[j]
for (int j = 0; j < vertexNum; j++)
{
//未访问、u可达、路过u可以使dis[j]更优
if (visited[j] == false && adjMatrix[u][j] != INFINITY && dis[u] + adjMatrix[u][j] < dis[j])
dis[j] = dis[u] + adjMatrix[u][j];
}
}
}/*邻接表版，复杂度O(V^2+E)*/
int vertexNum;
int dis[MAXN]; //dis[i]表示源点到i点的最小距离
bool visited[MAXN] = {false};
struct Edge{
int des; //边的目标顶点
int weight; //边的权值
};
vector<Edge> adjList[MAXN]; //邻接表
void dijkstra(int start)
{
for(int i = 0;i < vertexNum;i++)
{
dis[i] = INT_MAX;
}
dis[start] = 0;
for(int i = 0;i < vertexNum;i++)
{
int u = -1,minDis = INT_MAX;
for(int j = 0;j < vertexNum;j++)
{
if(visited[j] == false && dis[j] < minDis)
{
u = j;
minDis = dis[j];
}
}
if(u == -1)
return;
visited[u] = true;
for(int j = 0;j < adjList[u].size();j++)
{
//直接获得u能到达的点
int v = adjList[u][j].des;
if(visited[v] == false && dis[v] > dis[u] + adjList[u][j].weight)
{
dis[v] = dis[u] + adjList[u][j].weight;
}
}
}
}寻找\(dis[u]\)的循环可以用堆来优化，使得复杂度降为\(O(VlogV+E)\)。
Bellman-Ford
可以计算含有负权的边，检测是否存在一个从源结点可以到达的权重为负值的环路（负权环）：
bool bellmanFord(vector<vector<int>>& edge, vector<int>& dis, int start) {
for (int i = 0; i < dis.size(); ++i) {
if (i == start)
dis[i] = 0;
else
dis[i] = 0x3f3f3f3f;
}
for (int i = 0; i < dis.size(); ++i)
for (int j = 0; j < edge.size(); ++j)
dis[edge[j][1]] = min(dis[edge[j][1]], dis[edge[j][0]] + edge[j][2]);
bool negCycle = false;
for (int i = 0; i < edge.size(); ++i)
if (dis[edge[i][1]] > dis[edge[i][0]] + edge[i][2]) {
negCycle = true;
break;
}
return negCycle;
}复杂度\(O(VE)\)。
Floyd-Warshall
多源最短路径算法。
void floyd(vector<vector<int>>& m) {
for(size_t k = 0;k < m.size();++k)
for(size_t i = 0;i < m.size();++i)
for (size_t j = 0; j < m.size(); ++j) {
// m不能用INT_MAX初始化，会溢出，用0x3f3f3f3f
if (m[i][k] + m[k][j] < m[i][j])
m[i][j] = m[i][k] + m[k][j];
}
}不能用于含有负权环的图，这种图不存在最短路径。