【算法与数据结构】Dijkstra算法求单源最短路径问题

目录

Dijkstra算法

算法简介：

该算法的核心思想：

 算法特点：

算法示例演示：

算法实现： 

邻接矩阵存图

邻接表存图：

 时间复杂度分析：

---

Dijkstra算法

算法简介：

Dijkstra算法，是用来算出图中一个顶点到其余各顶点的最短路径。适合于解决带权的有向图中的单源最短路径问题。

该算法的核心思想：

• 声明一个dist数组来保存源点src到各个顶点的最短距离。dist[i]表示从顶点src到顶点i的最短距离。初始化时为无穷大。
• 采用贪心算法的思想，每次遍历距离始点最近且未被访问过的邻接节点。然后更新dist数组，直到扩展到终点。

 算法特点：

• 该算法使用了广度优先搜索解决赋权有向图或无向图的单源最短路径。
• Dijkstra算法要求图中所有边的权重非负，否则可能得到错误结果。

---

算法示例演示：

这里用邻接矩阵来存图， 邻接矩阵是一个二维数组，其中matrix[i][j]表示节点i到节点j的权重。

我们还需记录哪些节点已经访问过了，也就是哪些节点已经确定最短距离了。我们可以用一个bool类型的一维数组来记录。vector<bool> visited;  visited[i]=false表示顶点i还没有访问过。

初始化： 

  

开始更新，遍历每个节点，首先遍历节点v1。

• 先找出距离最小的顶点，也就是dist数组中的最小值，顶点v1。此时将visited[1]置为true，该顶点的最小路径已经确定。
• 这个顶点v1有出度，访问它的邻接节点，有v3,v5,v6三个节点。v1->v3=10,v1->v5=30,v1->v6=100。发现它们都比dist[3],dist[5],dist[6]要小，那么更新他们。

• 再次找出距离最小的顶点，去除顶点v1，因为v1的最短路径已经确定。发现是顶点v3，那么就可以更新dist[3]=10。此时v1到v3的距离就已经确定了，将visited[3]=true。

为什么？因为图中边权都是正数 ，目前离v1顶点最近的是顶点v3，那么肯定不可能通过第三个顶点中转，使得v1到v3的距离缩短，因为我们在开始选顶点的时候，v1到v3是最小的，也就是v1顶点到其他顶点的距离肯定没有v1到v3短。 

•  现在已经确定了一个顶点的最短路径，这个顶点v3有出度，去找它的邻接节点，发现有顶点v4，v1->v4的距离存储在dist[4]中，为INT_MAX，而v1->v3->v4=10+50=60，所以更新dist[4]为60。此时不能将 visited[4]置为true，因为这是我们通过v1->v3更新的v4，也有可能有其他更短的路径。

这一步可以总结为v1到v3的路程，即dist[3]，通过边v3->v4松弛成功，得到v1到v4的距离，这一步叫做松弛更新。通过“边”来松弛v1顶点到其余各个顶点的路程。这是该算法的核心。

 再次找出距离最小的顶点，除去顶点v1和顶点v3，因为这两个顶点已经确定最短路径。

发现dist[5]=30是最小的，和上面的解释原理相似，此时我们就可以确定出顶点v1到顶点v5的最短距离为30，vistied[5]置为true。

然后考虑v5的出度，也就是v5的邻接节点，我们发现v1->v5->v4的距离为30+20=50，小于dist[4]=60，那么更新dist[4]=50。还有v1->v5->v6=90，小于dist[6]=100，所以也更新dist[6]=100;  //松弛更新

 

然后再次找出距离最小的顶点，去除顶点v1,v3,v5。 发现是v4，那么visited[4]置为true，表示顶点4已经确定最短距离。

然后是考虑顶点4的出度，发现v1->v4->v6(v1->v5->v4->v6)=60，小于dist[6]，所以更新dist[6]=60。

最后再找距离最小的顶点，发现没有，说明所有顶点已经处理。最后的结果存于dist数组中，dist[i]就记录顶点v1到顶点i的最短路径，如果dist[i]=INT_MAX，说明顶点v1不可达顶点i。

算法结果：

v1到v1的最短距离：0

v1到v2的最短距离：不可达

v1到v3的最短距离：10

v1到v4的最短距离：50

v1到v5的最短距离：30

v1到v6的最短距离：60

---

算法实现： 

对以上过程总结如下：

1. 初始化：

   • dist 数组记录起点到各节点的最短距离，初始时除起点外均为 INF。

   • visited 数组标记节点是否已确定最短路径。

2. 循环处理所有节点：

   • 选择未访问的最小距离节点：遍历所有节点，找到当前距离最小的未访问节点 u。

   • 标记 u 为已访问：此时 u 的最短路径已确定。

   • 松弛操作：遍历所有节点 v，若存在边 u→v 且通过 u 的路径更短，则更新 dist[v]。

3. 终止条件：所有节点均被访问或剩余节点不可达。

这里会使用两种结构：邻接表和邻接矩阵。其中邻接表在稠密图中更高效，而邻接矩阵适合稀疏图。

邻接矩阵存图

以上图中的有向图为例。 （假设v1为源点)

//邻接矩阵存图
//.......
#include <iostream>
#include <vector>
using namespace std;const int INF = INT_MAX;
vector<int> dist;//记录最短路径
vector<int> parent;//记录父路径
void dijkstra(vector<vector<int>>& graph, int start_node)
{int n = graph.size();dist.resize(n, INF);parent.resize(n, -1);dist[start_node] = 0;vector<bool> visited(n, false);for (int i = 0; i < n; i++){//找到未访问节点中的距离最短的节点int u = -1;int min_dist = INF;for (int j = 0; j < n; j++){if (!visited[j] && dist[j] < min_dist){min_dist = dist[j];u = j;}}if (u == -1) break; //所有节点已处理visited[u] = true;//松弛更新//u->v  更新u所有邻接节点的距离for (int v = 0; v < n; v++){if (!visited[v] && graph[u][v] != INF)  //可达并且未处理过{if (dist[v] > dist[u] + graph[u][v]){//更新dist[v] = dist[u] + graph[u][v];parent[v] = u;}}}}
}
int main()
{//邻接矩阵表示图（INF表示不可达）vector<vector<int>> matrix = {{INF,INF,10,INF,30,100},{INF,INF,5,INF,INF,INF},{INF,INF,INF,50,INF,INF},{INF,INF,INF,INF,INF,10},{INF,INF,INF,20,INF,60},{INF,INF,INF,INF,INF,INF}};int n = matrix.size();int start_node = 0;dijkstra(matrix, start_node);// 输出结果cout << "从节点 " << start_node << " 到各节点的最短距离：" << endl;for (int i = 0; i < n; ++i) {if (dist[i] == INF)cout << "节点 " << i << ": 不可达" << endl;elsecout << "节点 " << i << ": " << dist[i] << endl;}//打印路径for (int i = 0; i < n; i++){if (i != start_node){vector<int> path;//逆序存储当前顶点的路径int parenti = i;while (parenti != -1){path.push_back(parenti);parenti = parent[parenti];}reverse(path.begin(), path.end());for (auto j : path){cout << j << "->";}cout << dist[i] << endl;}}return 0;
}

数组下标从0开始，所以与上面的演示结果编号相差1。

邻接表存图：

思路是一样的，只是这里我们可以使用优先级队列快速找到距离最短的边。

• 在邻接表的实现中，使用优先队列来处理节点，每次取出距离最小的节点，然后遍历其邻接表。
• 而在邻接矩阵中，每次处理节点u时，需要遍历所有可能的v，检查是否有边，并更新距离。

具体结构：

每个节点有一个vector存储相邻节点和对应的边权。使用pair<int,int>存储。

/ 定义图的邻接表结构：pair<相邻节点, 边权重>
typedef pair<int, int> Edge;
typedef vector<vector<Edge>> Graph;

Graph graph = {{{1, 4}, {2, 1}},    // 节点0的边：0→1（权4）、0→2（权1）{{3, 2}},             // 节点1的边：1→3（权2）{{1, 2}, {3, 5}},     // 节点2的边：2→1（权2）、2→3（权5）{{4, 3}},             // 节点3的边：3→4（权3）{}                    // 节点4的边：无};

然后，创建距离数组dist，初始化为无穷大，起点的距离设为0。

• 这里在找当前最短距离的节点时，为了快速找到距离最短的节点，我们可以使用优先级队列存储边，建小堆。C++的优先队列默认是最大堆，所以需要使用greater来转为最小堆。
• 在处理每个节点时，需要检查当前距离是否已经是最短，如果已经存在更短的路径，就跳过。否则，遍历所有邻接节点，更新它们的距离，并将新距离加入队列。
• 需要注意的是，可能有多个相同节点以不同距离存在于队列中，但一旦处理过更短的距离，后续的就可以忽略。因此，在取出节点时，需要检查当前记录的距离是否小于队列中的距离，如果是，就跳过。

//邻接表存图
//......
#include <iostream>
#include <vector>
#include <queue>
using namespace std;//pair<相邻节点, 边权重>
typedef pair<int, int> Edge;
typedef vector<vector<pair<int, int>>> Graph;
vector<int> dijkstra(const Graph& graph, int start)
{int n = graph.size();vector<int> dist(n, INT_MAX);      // 存储起点到各节点的最短距离priority_queue<Edge, vector<Edge>, greater<Edge>> pq; // 小顶堆：按距离排序dist[start] = 0;pq.push({ 0,start });//初始节点入队while (!pq.empty()){int u = pq.top().second;      // 当前距离最小的节点int curr_dist = pq.top().first;pq.pop();// 如果当前路径不是最短的，跳过处理if (curr_dist > dist[u]) continue;// 遍历u的所有邻接节点vfor (const Edge& edge : graph[u]) {int v = edge.first;       // 邻接节点int weight = edge.second; // 边权重// 如果通过u到v的路径更短，则更新距离if (dist[v] > dist[u] + weight){dist[v] = dist[u] + weight;pq.push({ dist[v], v }); // 将新距离加入队列}}}return dist;
}
int main()
{// 图的邻接表表示（有向图）Graph graph = {{{1, 4}, {2, 1}},    // 节点0的边：0→1（权4）、0→2（权1）{{3, 2}},             // 节点1的边：1→3（权2）{{1, 2}, {3, 5}},     // 节点2的边：2→1（权2）、2→3（权5）{{4, 3}},             // 节点3的边：3→4（权3）{}                    // 节点4的边：无};int start_node = 0;vector<int> dist= dijkstra(graph, start_node);// 输出结果cout << "从节点 " << start_node << " 到各节点的最短距离：" << endl;for (int i = 0; i < dist.size(); ++i) {if (dist[i] == INT_MAX)cout << "节点 " << i << ": 不可达" << endl;elsecout << "节点 " << i << ": " << dist[i] << endl;}return 0;
}

 

 时间复杂度分析：

V是顶点数，E是边数。

邻接矩阵实现的时间复杂度是O(V^2)，而使用优先队列的邻接表实现是O((V+E)logV)。因此，在稀疏图中，邻接表的效率更高，但邻接矩阵可能在代码上更简单，尤其是对于稠密图。