算法思想简述(From C知道):
Dijkstra算法是一种求解最短路径的贪心算法,它能够找到两点之间的最短路径。C语言实现Dijkstra算法需要以下步骤:
1. 创建一个数组用于记录起始点到其他节点的距离,初始化为无穷大。
2. 创建一个数组用于记录节点是否已经被访问过,初始化为false。
3. 将起始点到自身的距离设为0。
4. 遍历图中所有节点,对于每个节点:
1) 找到起始点到该节点距离最短的节点(即未被访问过且距离最小的节点)。
2) 标记该节点已经被访问过。
3) 遍历该节点的所有邻居节点,更新起始点到邻居节点的距离。
5. 最终得到起始点到其他所有节点的最短距离。
dijkstra函数代码实现:
int n, m, s, e; // 节点数, 有向线段数, 起点, 终点
int graph[size][size]; // 图的邻接矩阵
int dist[size]; // 起点到各点的最短距离
bool visited[size]; // 记录节点是否被访问过void dijkstra(int s)
{for(int i=1; i<=n; i++) // 初始化距离和访问状态{dist[i] = max;visited[i] = false;}dist[s] = 0; // 起点到自身的距离为0for(int i=1; i<=n; i++) // 遍历所有节点{int min = max, u = -1;for(int j=1; j<=n; j++) // 找到未访问节点中距离起点最近的节点{if(dist[j] < min && !visited[j]){u = j; min = dist[j];//可以用i=1的情况来理解,找到离原点最近的一个节点}}if(u == -1) return; // 若未找到可达节点,退出循环visited[u] = true; // 标记节点u为已访问for(int v=1; v<=n; v++) // 更新起点到各节点的距离{//从原点先到u再到v的路径 < 原先记录的从原点到v的路径 //u,v之间有通路if(dist[v] > dist[u] + graph[u][v] && !visited[v] && graph[u][v] != max) { //v尚未访问过dist[v] = dist[u] + graph[u][v];}}}
}
整体程序代码实现:
#include<bits/stdc++.h>
using namespace std;
#define size 1000 // 定义图的最大节点数
#define max 1000000000 // 定义最大值
int n, m, s, e; // 节点数, 有向线段数, 起点, 终点
int graph[size][size]; // 图的邻接矩阵
int dist[size]; // 起点到各点的最短距离
bool visited[size]; // 记录节点是否被访问过void dijkstra(int s)
{for(int i=1; i<=n; i++) // 初始化距离和访问状态{dist[i] = max;visited[i] = false;}dist[s] = 0; // 起点到自身的距离为0for(int i=1; i<=n; i++) // 遍历所有节点{int min = max, u = -1;for(int j=1; j<=n; j++) // 找到未访问节点中距离起点最近的节点{if(dist[j] < min && !visited[j]){u = j; min = dist[j];//可以用i=1的情况来理解,找到离原点最近的一个节点}}if(u == -1) return; // 若未找到可达节点,退出循环visited[u] = true; // 标记节点u为已访问for(int v=1; v<=n; v++) // 更新起点到各节点的距离{//从原点先到u再到v的路径 < 原先记录的从原点到v的路径 //u,v之间有通路if(dist[v] > dist[u] + graph[u][v] && !visited[v] && graph[u][v] != max) { //v尚未访问过dist[v] = dist[u] + graph[u][v];}}}
}int main()
{cout<<"依次输入节点数, 有向线段数, 起点, 终点(数字间以空分隔): ";cin>>n>>m>>s>>e; // 输入节点数, 有向线段数, 起点, 终点for(int i=1; i<=n; i++) // 初始化图的邻接矩阵{for(int j=0; j<=n; j++){graph[i][j] = i==j ? 0: max;} }int u, v, wt;for(int i=1; i<=m; i++) // 输入有向线段的起点、终点和权重{cin>>u>>v>>wt;graph[u][v] = wt;graph[v][u] = wt; // 无向图,对称设置权重}dijkstra(s); // 调用Dijkstra算法求最短路径cout<<"min_track_length: "<<dist[e]; // 输出起点到终点的最短距离return 0;
}
送上测试数据一份:
/*
测试数据:
5 6 1 5
1 2 4
2 5 10
1 3 5
3 2 1
3 4 2
4 5 6
*/
~~ 希望对你有帮助 ~~