C++的算法：Dijkstra算法与Floyd算法的原理及应用
在计算机科学中，图论是一个重要的分支，它涉及到网络、路径查找、最短路径等多种问题。Dijkstra算法和Floyd算法是图论中常用的两种算法，分别用于单源最短路径问题和所有顶点对之间的最短路径问题。下面我们将详细解释这两种算法的原理，并通过实例展示其应用。
一、Dijkstra算法
Dijkstra算法用于解决带权重的有向图或无向图中的单源最短路径问题。该算法的基本思想是以起始点为中心向外层层扩展，直到扩展到终点为止。
原理：
1. 初始化：将所有节点的距离设为无穷大（除了起始节点设为0）。
2. 选择当前距离最小的节点作为扩展节点。
3. 更新该节点所有邻居节点的距离。
4. 重复步骤2和3，直到所有节点都被处理过。
示例：
假设我们有一个带权重的无向图，起始节点为A，目标为D。边的权重表示两点之间的距离。
A—1—B—3—C
| |
4 2
| |
E—5—D
代码如下。
#include
#include
#include
using namespace std;
void dijkstra(vector<vector<pair>>& graph, int start) {
int numVertices = graph.size();
vector distances(numVertices, numeric_limits::max());
distances[start] = 0;
vector visited(numVertices, false);
for (int count = 0; count < numVertices - 1; count++) {
int minDist = numeric_limits::max(), minIndex;
for (int vertex = 0; vertex < numVertices; vertex++)
if (distances[vertex] <= minDist && !visited[vertex])
minDist = distances[vertex], minIndex = vertex;
visited[minIndex] = true;
for (auto neighbor : graph[minIndex]) {
int neighborIndex = neighbor.first;
int weight = neighbor.second;
if (!visited[neighborIndex] && distances[minIndex] != numeric_limits::max() &&
distances[minIndex] + weight < distances[neighborIndex])
distances[neighborIndex] = distances[minIndex] + weight;
}
}
// 输出最短路径
for (int i = 0; i < numVertices; i++)
cout << "Distance from start to " << i << " is " << distances[i] << endl;
}
int main() {
vector<vector<pair>> graph = {
{{1, 1}, {4, 4}},
{{0, 1}, {2, 3}, {3, 5}},
{{1, 3}},
{{1, 2}, {2, 5}},
{{1, 4}, {3, 5}}
};
dijkstra(graph, 0);
return 0;
}运行这段代码，我们得到从A到其他所有节点的最短距离。
应用：
1. 地图应用中计算两点之间的最短路径。
2. 网络路由协议中计算最佳路径。
3. 物流管理中计算最低成本的运输路径。
二、Floyd算法
Floyd算法用于计算图中所有顶点对之间的最短路径。该算法基于动态规划的思想，通过迭代更新顶点对之间的最短路径。
原理：
1. 初始化：对于任意两个顶点i和j，如果它们之间存在一条边，则dist[i][j]为该边的权重；否则dist[i][j]为无穷大。对于每个顶点i，dist[i][i]为0。
2. 对于每一对顶点k和i，遍历所有顶点j，如果通过顶点k从i到j的路径比已知的路径更短，则更新dist[i][j]。
3. 重复步骤2，直到dist数组不再发生变化。
示例：
以下是一个简单的加权有向图，我们要求出所有顶点对之间的最短路径。
A–3–B
| |
5\ | 2/
| v
C—-1—-D
\ /|
4 / |
E–1–F
代码如下。
#include
#include
#include
using namespace std;
void floyd(vector<vector>& graph, int V) {
vector<vector> dist(V, vector(V, INT_MAX));
// 初始化dist数组
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (graph[i][j] != 0)
dist[i][j] = graph[i][j];
else if (i == j)
dist[i][j] = 0;
}
}
// Floyd算法的核心部分
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// 输出所有顶点对之间的最短距离
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INT_MAX)
cout << "INF" << " ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
int main() {
int V = 6; // 顶点数量
vector<vector> graph = {
{0, 3, INT_MAX, 5, INT_MAX, INT_MAX},
{INT_MAX, 0, 2, INT_MAX, INT_MAX, 4},
{INT_MAX, INT_MAX, 0, 1, INT_MAX, INT_MAX},
{INT_MAX, INT_MAX, INT_MAX, 0, 1, INT_MAX},
{INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, 1},
{INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0}
};
floyd(graph, V);
return 0;
}在这段代码中，`graph`矩阵用来存储图中所有顶点对之间的权重，其中`INT_MAX`表示两个顶点之间没有直接连接的边。
应用：
1. 在计算机网络中计算任意两个节点之间的最短路径。
2. 在物流规划中找出任意两点之间最经济、时间最短的路线。
3. 旅行商问题（TSP）中，通过Floyd算法计算所有城市对之间的最短距离，进而寻找最短旅行路线。
请注意，Floyd算法在稠密图中效率较高，而在稀疏图中可能不如Dijkstra算法或其他算法效率高。在实际应用中，需要根据图的特性选择合适的算法。
综上所述，Dijkstra算法和Floyd算法在解决图论中的最短路径问题方面各有其特点和应用场景。通过理解它们的原理和实现方式，我们可以更好地应用它们来解决实际问题。
