[C++][数据结构][图][下][最短路径]详细讲解

1.最短路径

最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小

1.单源最短路径 – Dijkstra算法

时间复杂度： $O(N^2)$ ，空间复杂度： $O (N)$
**单源最短路径问题：**给定一个图 $G = (V, E)$ ，求源结点 $s \in V$ 到图中每个结点 $v \in V$ 的最短路径
- Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题
- 同时算法要求图中所有边的权重非负
- 一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径
Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新，并加入S中，所以该算法使用的是贪心策略
- Dijkstra去找最小起始边
- Dijkstra的贪心策略：每次去选从s -> #，最短路径边的那个顶点，去更新其连接的路径，u是不是在S中的点
针对一个带权有向图G，将所有结点分为两组S和Q
- S是已经确定最短路径的结点集合，在初始时为空
  - 初始时就可以将源节点s放入，毕竟源节点到自己的代价是0)
- Q为其余未确定最短路径的结点集合，每次从Q中找出一个起点到该结点代价最小的结点u，将u从Q中移出，并放入S中，对u的每一个相邻结点v进行松弛操作
- 如此一直循环直至集合Q为空
  - 即：所有节点都已经查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值，不发生变化
松弛：
- 对每一个相邻结点v ，判断源节点s到结点u的代价与u到v的代价之和是否比原来s到v的代价更小
  - srci->u + u->v < srci->v
- 若代价比原来小，则要将s到v的代价更新为s到u与u到v的代价之和，否则维持原样
Dijkstra算法存在的问题是不支持图中带负权路径
- 如果带有负权路径，则可能会找不到一些路径的最短路径
在下图Dijkstra算法的执行过程
- 源节点s为最左边的结点
- 每个结点中的数值为该结点的最短路径的估计值
- 加了阴影的边表明前驱值
- 黑色的结点属于集合S

// 比较抽象，对着图和文档会好理解些:P
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
	size_t srci = GetVertexIndex(src);
	size_t n = _vertexs.size();

	dist.resize(n, MAX_W); // dist[] 存储src -> *的最短路径
	pPath.resize(n, -1); // pPath 存储路径前一个顶点下标

	dist[srci] = 0;
	pPath[srci] = srci;

	// 已经确定最短路径的顶点集合
	vector<bool> S(n, false);

	for (size_t i = 0; i < n; i++) // n个顶点
	{
		// 选最短路径且不在S的顶点，更新其他路径
		int u = 0;
		W min = MAX_W;
		for (size_t j = 0; j < n; j++)
		{
			if (S[j] == false && dist[j] < min)
			{
				u = j;
				min = dist[j];
			}
		}
		S[u] = true;

		// 松弛更新u连接顶点v  srci->u + u->v  <  srci->v  更新
		for (size_t v = 0; v < n; v++)
		{
			if (S[v] == false && _matrix[u][v] != MAX_W
				&& dist[u] + _matrix[u][v] < dist[v])
			{
				dist[v] = dist[u] + _matrix[u][v];
				pPath[v] = u;
			}
		}
	}
}

void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
{
	size_t srci = GetVertexIndex(src);
	size_t n = _vertexs.size();

	for (size_t i = 0; i < n; i++)
	{
		if (i != srci)
		{
			// 找出i顶点的路径
			vector<int> path;
			size_t parenti = i;

			while (parenti != srci)
			{
				path.push_back(parenti);
				parenti = pPath[parenti];
			}
			path.push_back(srci);
			reverse(path.begin(), path.end());

			for(auto index : path)
			{
				cout << _vertexs[index] << "->";
			}
			cout << dist[i] << endl;
		}
	}
}

2.单源最短路径 – Bellman-Ford算法

时间复杂度：O(N^3) 空间复杂度：O(N)
Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图，此时这个算法就不能帮助我们解决问题了，而Bellman-Ford算法可以解决负权图的单源最短路径问题
Bellman-Ford找终止边，是个暴力求解算法
优点：
- 可以解决有负权边的单源最短路径问题
- 可以用来判断是否有负权回路
缺点：时间复杂度： $O (N * E)$
- N是点数，E是边数
- 普遍是要高于Dijkstra算法O(N²)的
- 此处如果使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是 $O(N^3)$
- 这里也可以看出来Bellman-Ford就是一种暴力求解更新
**思路梳理：**可能权值和路径对不上
- 只要更新出了一条更短路径，可能就会影响其他路径
- 再更新一次就修正了，但是新更新的路径又可能会影响其他路径
- 所以还要继续更新，最多更新n轮
优化：
- 循环提前跳出
- 队列优化 – SPFA
  - 所有边入队列
  - 后面的轮次：更新最短路径的边入队列
注意：负权回路，神仙难救，求不出最短路径
在下图执行Bellman-Ford算法过程
- 源节点为s，结点中的数值为该节点的distance值
- 加了阴影的边表示前驱值
- 如果边 $(u, v)$ 加了阴影，则 $v .Π = u$
- 在本图例子中，每一次松弛操作对边的处理次序都是：
  - $(t, x) ， (t, y) ， (t, x) ， (y, x) ， (y, z) ， (z, x) ， (z, s) ， (s, t) ， (s, y)$
- (a)在第一次松弛操作前的场景，(b)~(e)在对边进行每次松弛操作后的场景，(e)中的d值和 $Π$ 值为最终取值
- 在本例中，Bellman-Ford算法返回值为TRUE

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
    size_t n = _vertexs.size();
    size_t srci = GetVertexIndex(src);

    dist.resize(n, MAX_W);
    pPath.resize(n, -1);

    // 先更新srci->srci为缺省值
    dist[srci] = W();

    // 总体最多更新n轮
    for (size_t k = 0; k < n; k++)
    {
        bool update = false;

        // i->j松弛
        for (size_t i = 0; i < n; i++)
        {
            for (size_t j = 0; j < n; j++)
            {
                // srci -> i + i -> j
                if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
                {
                    dist[j] = dist[i] + _matrix[i][j];
                    pPath[j] = i;

                    update = true;

                    cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
                }
            }
        }

        // 如果这个伦茨中没有更新出更短路径，那么后续轮次就不需要走了
        if (!update)
        {
            break;
        }
    }

    // 还能更新，则为带负权回路
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            // srci -> i + i -> j
            if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
            {
                return false;
            }
        }
    }

    return true;
}

3.多源最短路径 – Floyd-Warshall算法

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法
- 以所有点为源点，求出任意两点之间的距离
Floyd-Warshall算法考虑的是一条最短路径的中间节点
- 即：简单路径 $p=\{v1,v2,…,vn\}$ 上除 $v_1$ 和 $v_n$ 的任意节点
设k是p的一个中间节点，那么从 $i - > j$ 的最短路径p就被分成 $i - > k$ 和 $k - > j$ 的两段最短路径 $p_1$ ， $p_2$
- $p_1$ 是从 $i - > k$ 且中间节点属于 ${1，2，…，k-1\}$ 取得的一条最短路径
- $p_2$ 是从 $k - > j$ 且中间节点属于 ${1， 2，…，k-1\}$ 取得的一条最短路径
下图中
- 路径p是 $i - > j$ 的一条最短路径，结点k是路径p上编号最大的中间节点
- 路径 $p_1$ 是路径p上 $i - > k$ 之间的一段，其所有中间节点取自集合 ${1， 2，…，k-1\}$
- $k - > j$ 的路径 $p_2$ 也遵守同样的规则

原理

Floyd-Warshall算法的原理是动态规划
- 在实际算法中，为了节约空间，可以直接在原来的空间上进行迭代，这样空间可降至二维
即：Floyd算法本质是三维动态规划， $D [i] [j] [k]$ 表示 $i - > j$ 只经过0到k个点最短路径，然后建立起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得到所以点的最短路径

void FloydWarshall(vector<vector<W>>& dist, vector<vector<int>>& pPath)
{
	size_t n = _vertexs.size();
	dist.resize(n);
	pPath.resize(n);

	// 初始化权值和路径矩阵
	for (size_t i = 0; i < n; i++)
	{
		dist[i].resize(n, MAX_W);
		pPath[i].resize(n, -1);
	}

	// 首先直接相连的边更新
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < n; j++)
		{
			if (_matrix[i][j] != MAX_W)
			{
				dist[i][j] = _matrix[i][j];
				pPath[i][j] = i;
			}

			if (i == j)
			{
				dist[i][j] = W();
			}
		}
	}

	// 最短路径的更新 i -> {else} -> j
	for (size_t k = 0; k < n; k++)
	{
		for (size_t i = 0; i < n; i++)
		{
			for (size_t j = 0; j < n; j++)
			{
				// k作为i j的中间点，尝试去更新i->j的路径
				if (dist[i][k] != MAX_W && dist[k][j] != MAX_W
					&& dist[i][k] + dist[k][j] < dist[i][j])
				{
					dist[i][j] = dist[i][k] + dist[k][j];

					// 找跟j相连的上一个邻接顶点，k j不一定是直接相连的
					// 如果k->j 直接相连，pPath[k][j]存的就是k
					// 如果k->j 没有直接相连，k->...->x->j，pPath[k][j]村的就是x
					pPath[i][j] = pPath[k][j];
				}
			}
		}
	}
}