算法思想简述（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; // 起点到自身的距离为0
for(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; // 起点到自身的距离为0
for(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
*/~~ 希望对你有帮助 ~~
