数据结构 —— Dijkstra算法

在上次的博客中，我们解决了使用最小的边让各个顶点连通（最小生成树）
这次我们要解决的问题是现在有一个图，我们要找到一条路，使得从一个顶点到另一个顶点路径权值之和最小（比如：找到从小潮到胖迪最短的一条路径）：

我们可以看出来，小潮->小傲->胖迪这条路径是最短的。

而我们今天学的算法，Dijkstra，就是完成这样的工作的：

Dijkstra算法

Dijkstra算法是一种用于寻找图中两个节点之间的最短路径的算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年发明。该算法的基本思想是使用贪心策略，从起始节点开始，逐步扩展到距离它最近的未访问过的节点，直到目标节点被访问。

以下是Dijkstra算法的基本步骤：

1. 初始化：将起点到所有其他节点的距离设为无穷大（表示还未计算），除了起点到自身的距离为0。创建一个空的已访问节点集合和一个包含所有节点的未访问节点集合。

2. 从未访问节点集合中选择距离起点最近的节点，将其标记为已访问，并更新其邻接节点的距离。如果某个邻接节点的距离通过当前节点更短，则更新该邻接节点的距离。

3. 重复步骤2，直到找到目标节点或未访问节点集合为空。

4. 如果找到了目标节点，则返回从起点到目标节点的最短路径；否则，说明起点和目标节点之间不存在路径。

需要注意的是，Dijkstra算法只适用于没有负权重边的图，因为负权重边会导致算法无法正确地确定最短路径。此外，Dijkstra算法的时间复杂度为O(ElogV)，其中E表示边的数量，V表示节点的数量。在实际应用中，可以使用优先队列等数据结构来优化算法的时间复杂度。

我们将上面的图改造复杂一点，这样可以看出Dijkstra算法的高效：

void TestGraph2()
	{
		string a[] = {"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};
		Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));
		g1.AddEdge("小潮", "小傲", 30);
		g1.AddEdge("小潮", "高斯", 83);
		g1.AddEdge("小潮", "海皇", 34);
		g1.AddEdge("胖迪", "海皇", 78);
		g1.AddEdge("胖迪", "小傲", 76);
		g1.AddEdge("小杨", "皖皖", 54);
		g1.AddEdge("小杨", "高斯", 48);
		g1.AddEdge("高斯", "皖皖", 55);
		g1.AddEdge("胖迪", "高斯", 70);
		g1.AddEdge("小傲", "海皇", 3);

		g1.Print();
		cout << endl;

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

划分集合

Dijkstra算法中，提到我们要划分集合一个是访问过的集合，一个是没有被访问过的集合，假设我们从小潮开始：

我们可以用一个bool的数组，访问过了的标记为true，没有为false。
假设我们要从小潮到胖迪，我们要计算路径之和，我们还需要一个数组存放到各个顶点边的权值：

同时，如果我们想打印路径出来，我们还要一个数组存放路径（这里有点像并查集里面的操作）：

模拟过程

假设我们从小潮开始，各个数组情况如下：

现在，扫描跟小潮相连的边，最小的权值相关结点标记：

现在我们从小傲出发，发现海皇近，跳到海皇，发现总路径之和为33，比原来34小，故更新，并标记：

我们代码实现一下：

    void Dijkstra(const V& srci, vector<W>& dest, vector<int>& parentPath )
    {
        // 将源节点转换为其在顶点列表中的索引
        int srcIndex = FindSrci(srci);

        // 初始化parentPath向量，用于记录最短路径上的前驱节点，初始值为-1表示未访问
        parentPath.resize(_vertex.size(), -1);

        // 初始化dest向量，用于记录从源节点到每个节点的最小距离，初始值为最大权重MAX_W
        dest.resize(_vertex.size(), MAX_W);

        // 给源节点赋值为0，表示从源节点到自身距离为0
        dest[srcIndex] = W();

        // 初始化一个布尔型向量，用于记录每个节点是否已被访问，初始值为false
        vector<bool> isVisted;
        isVisted.resize(_vertex.size(), false);

        // 主循环，迭代次数为顶点数
        for (size_t i = 0; i < _vertex.size(); i++)
        {
            // 初始化最小距离为最大权重MAX_W
            W min = MAX_W;
            size_t u = srcIndex;

            // 寻找未被访问且具有最小dest值的节点u
            for (size_t j = 0; j < _vertex.size(); j++)
            {
                if (isVisted[j] == false && dest[j] < min)
                {
                    min = dest[j];
                    u = j;
                }
            }

            // 标记节点u为已访问
            isVisted[u] = true;

            // 对节点u的所有邻居进行松弛操作
            for (size_t i = 0; i < _vertex.size(); i++)
            {
                // 只处理未被访问的邻居，并且存在从u到i的边（_matrix[u][i] != MAX_W）
                if (isVisted[i] == false && _matrix[u][i] != MAX_W
                    && dest[u] + _matrix[u][i] < dest[i])
                {
                    // 更新从源节点到节点i的最小距离
                    dest[i] = dest[u] + _matrix[u][i];
                    // 更新节点i的前驱节点为u
                    parentPath[i] = u;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

打印路径

打印路径记得一点，最后我们要逆置一下：

    // 打印从源节点到所有其他节点的最短路径
    void PrintShortestPath(const V& src, const vector<W>& dist, const vector<int>& parentPath)
    {
        // 将源节点转换为其在顶点列表中的索引
        size_t srcIndex = FindSrci(src);

        // 遍历所有顶点
        for (size_t i = 0; i < _vertex.size(); i++)
        {
            // 跳过源节点本身
            if (i == srcIndex)
                continue;

            // 创建一个vector，用于存储从目标节点到源节点的路径
            vector<int> path;
            // 当前处理的节点初始化为目标节点
            size_t current = i;

            // 从目标节点出发，回溯到源节点，构建路径
            while (current != srcIndex)
            {
                // 将当前节点添加到路径vector中
                path.push_back(current);
                // 将当前节点设置为其前驱节点，继续回溯
                current = parentPath[current];
            }
            // 最后将源节点添加到路径vector中
            path.push_back(srcIndex);

            // 翻转路径vector，使得路径顺序从源节点到目标节点
            reverse(path.begin(), path.end());

            // 输出路径和对应的最短距离
            for (auto node : path)
            {
                // 输出路径中的每个节点
                cout << _vertex[node] << "->";
            }
            // 输出从源节点到目标节点的最短距离
            cout << dist[i] << endl;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42