C++实现邻接矩阵狄克斯特拉算法求最短路径 |21xrx.com

C++实现邻接矩阵狄克斯特拉算法求最短路径

2023-07-11 04:18:28 深夜i -- --

C++ 邻接矩阵狄克斯特拉算法最短路径求解

狄克斯特拉算法（Dijkstra’s Algorithm）是解决单源最短路径问题的一种有效算法。在计算机科学中，一个图可以用邻接矩阵来表示。因此，在C++中，使用邻接矩阵来实现狄克斯特拉算法是一种广泛采用的方法。

邻接矩阵是一个二维的布尔型数组Matrix[][],其中 Matrix[A][B] == 1 表示从顶点A到顶点B有一条边，否则则为 0 或者 INF (无穷大)。如果顶点i到顶点j有权值，则Matrix[i][j]就是这个权值，否则Matrix[i][j]为INF。

邻接矩阵狄克斯特拉算法的基本思路是：从起点开始，先将所有点的路径长度初始化为无穷大，再以起点为基础，计算起点到每个点的距离，将路径长度存储下来。当每个点的路径长度都确定后，再开始找到组成最短路径的节点。

// C++实现邻接矩阵狄克斯特拉算法求最短路径

#include

using namespace std;

#define V 9 // 顶点个数

int minDistance(int dist[], bool sptSet[]) {

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

}

void printSolution(int dist[]) {

cout << "Vertex \t Distance from Source\n";

for (int i = 0; i < V; i++)

cout << i << " \t\t " << dist[i] << "\n";

}

void dijkstra(int graph[V][V], int src) {

int dist[V];

bool sptSet[V];

for (int i = 0; i < V; i++)

dist[i] = INT_MAX, sptSet[i] = false;

dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

int u = minDistance(dist, sptSet);

sptSet[u] = true;

for (int v = 0; v < V; v++)

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

}

printSolution(dist);

}

int main() {

int graph[V][V] = { 0,

11,

};

dijkstra(graph, 0);

return 0;

}

在这个例子中，我们假设有九个节点，从0到8依次排列。我们定义邻接矩阵为graph，其中 graph[i][j]代表从顶点i到顶点j的边权值。我们开始选择节点 0 作为起点，执行狄克斯特拉算法，最终输出每个节点到起点的最短距离。

在这个算法实现中，我们使用了一个minDistance函数来找到距离起点最近的节点，然后用printSolution函数输出结果。我们也定义了dist数组来存储每个节点到起点的距离，并使用sptSet数组来表示节点是否已经被访问过。

总之，邻接矩阵狄克斯特拉算法是一种实际应用广泛的算法，并且在C++中的实现也相对简单明了。通过使用这个算法，我们可以找到从起点到每个节点的最短路径，帮助我们在实际情况中处理大量的路线和路径问题。

上一篇: idea打包java可执行jar包

下一篇: VC++6.0的文件保存方法

评论区

()

相似文章