Dijkstra算法，用于求解图中从一个起点到其他所有节点的最短路径。解决单源最短路径问题的有效方法。
条件
有向
带权路径
时间复杂度 O（n平方）
方法步骤
1 把图上的点分为两个集合 要求的起点 和除了起点之外的点 。能直达的写上权值 不能直达的写上无穷 自己到自己的距离是0
2 在除起点以外的中找权值最小的顶点，这个顶点加入起点所在的集合。由于新顶点的并入，可以把新顶点作为中转点，再重新计算起点到所有除已经并入顶点的距离，找最小的继续并入，直到所有顶点并入起点所在的集合。
以下是对代码的详细解析和注释：
代码解析
全局变量定义
#define N 1005 // 定义最大顶点数为1005
int n, m; // n表示顶点数，m表示边数
bool str[N]; // 用于标记是否已确定最短路径
int dis[N]; // 存储从起始点到各个顶点的最短距离
int g[N][N]; // 邻接矩阵，存储图的结构-
N：定义图中最大顶点数为1005。 -
n和m：分别表示图中的顶点数和边数。 -
str：布尔数组，用于标记某个顶点是否已经确定了最短路径。 -
dis：数组，存储从起点到每个顶点的最短距离。 -
g：邻接矩阵，g[i][j]表示从顶点i到顶点j的距离。
Dijkstra算法实现
void dijkstra() {// 初始化dis数组为一个很大的值（这里选择0x3f3f3f3f）memset(dis, 0x3f3f3f3f, sizeof(dis));// 起始点到自身的距离为0dis[1] = 0;for (int i = 1; i <= n; ++i) {int temp = -1; // 选择未确定的顶点// 寻找当前未确定的最小距离顶点for (int j = 1; j <= n; ++j)if (!str[j] && (temp == -1 || dis[j] < dis[temp]))temp = j;// 更新与该顶点相邻的其他顶点的距离for (int j = 1; j <= n; ++j)dis[j] = min(dis[j], dis[temp] + g[temp][j]);// 标记该顶点已经确定了最短路径str[temp] = true;}// 输出结果for (int i = 1; i <= n; ++i) {if (dis[i] == 0x3f3f3f3f)cout << "-1" << " "; // 如果没有到该顶点的路径则输出-1elsecout << dis[i] << " "; // 否则输出最短距离}
}-
初始化：
-
memset(dis, 0x3f3f3f3f, sizeof(dis));：将dis数组初始化为一个很大的值（0x3f3f3f3f），表示初始时从起点到其他顶点的距离是无穷大。 -
dis[1] = 0;：将起点到自身的距离设置为0。
-
-
主循环：
-
for (int i = 1; i <= n; ++i)：循环n次，每次找到一个未确定最短路径的顶点。 -
int temp = -1;：初始化当前未确定的最短距离顶点为 -1。 -
for (int j = 1; j <= n; ++j)：遍历所有顶点，找到未确定最短路径的顶点中距离最短的顶点temp。-
if (!str[j] && (temp == -1 || dis[j] < dis[temp]))：如果顶点j未确定最短路径且距离更短，则更新temp。
-
-
for (int j = 1; j <= n; ++j)：更新与顶点temp相邻的其他顶点的距离。-
dis[j] = min(dis[j], dis[temp] + g[temp][j]);：如果通过temp到达j的距离更短，则更新dis[j]。
-
-
str[temp] = true;：标记顶点temp已经确定了最短路径。
-
-
结果输出：
-
遍历
dis数组，输出从起点到每个顶点的最短距离。 -
如果
dis[i]仍然是0x3f3f3f3f，表示没有路径到达顶点i，输出-1。 -
否则输出
dis[i]。
-
主函数
int main() {// 初始化邻接矩阵g为一个很大的值memset(g, 0x3f3f3f3f, sizeof(g));// 输入顶点数n和边数mcin >> n >> m;while (m--) { // 处理每一条边的输入int x, y, z;cin >> x >> y >> z;// 更新邻接矩阵g中的权值g[x][y] = min(g[x][y], z);}// 调用dijkstra函数求解dijkstra();return 0;
}-
初始化邻接矩阵：
-
memset(g, 0x3f3f3f3f, sizeof(g));：将邻接矩阵g初始化为一个很大的值（0x3f3f3f3f），表示初始时图中没有边。
-
-
输入图的边：
-
cin >> n >> m;：读取顶点数n和边数m。 -
while (m--)：循环m次，读取每一条边的信息。-
cin >> x >> y >> z;：读取边的起点x、终点y和权重z。 -
g[x][y] = min(g[x][y], z);：更新邻接矩阵g中的权值，如果有多条边连接同一对顶点，只保留权重最小的那条边。
-
-
-
调用Dijkstra算法：
-
dijkstra();：调用dijkstra函数求解最短路径。
-
-
输出结果：
-
dijkstra函数会输出从起点到每个顶点的最短距离。
-
示例输入和输出
示例输入
5 7
1 2 4
1 3 3
2 4 2
3 2 1
3 4 5
4 5 1
2 5 7示例输出
0 2 3 4 5
解释
-
顶点 1 到顶点 2 的最短距离为 2（1 -> 3 -> 2）。
-
顶点 1 到顶点 3 的最短距离为 3（1 -> 3）。
-
顶点 1 到顶点 4 的最短距离为 4（1 -> 3 -> 2 -> 4）。
-
顶点 1 到顶点 5 的最短距离为 5（1 -> 3 -> 2 -> 4 -> 5）。
关键点总结
-
邻接矩阵：使用二维数组
g[N][N]表示图的结构，g[i][j]表示从顶点i到顶点j的距离。 -
选择最短距离顶点：通过遍历所有顶点，找到未确定最短路径的顶点中距离最短的顶点。
-
更新邻接顶点的距离：通过当前顶点更新其邻接顶点的距离。
-
标记顶点：使用布尔数组
str标记顶点是否已经确定了最短路径。
Dijkstra算法详细步骤解析
1. 初始化
在算法开始之前，需要进行以下初始化操作：
-
初始化距离数组
dis：-
将
dis数组中的所有元素初始化为一个很大的值（如0x3f3f3f3f），表示从起点到其他顶点的距离初始为无穷大。 -
将起点的距离设置为 0，即
dis[start] = 0。
-
-
初始化访问标记数组
str：-
将
str数组中的所有元素初始化为false，表示所有顶点初始时都未被访问过。
-
-
初始化邻接矩阵
g：-
将邻接矩阵
g中的所有元素初始化为一个很大的值（如0x3f3f3f3f），表示初始时图中没有边。
-
2. 主循环
Dijkstra算法的核心是一个主循环，该循环执行 n 次（n 为顶点数），每次找到一个未访问的最短距离顶点，并更新其邻接顶点的距离。
-
选择未访问的最短距离顶点：
-
遍历所有顶点，找到未访问的顶点中距离最短的顶点
u。 -
如果所有顶点都已被访问过，或者没有找到未访问的顶点，则退出循环。
-
-
更新邻接顶点的距离：
-
遍历顶点
u的所有邻接顶点v，如果通过u到达v的距离更短，则更新dis[v]。 -
具体来说，如果
dis[u] + g[u][v] < dis[v]，则更新dis[v] = dis[u] + g[u][v]。
-
-
标记顶点为已访问：
-
将顶点
u标记为已访问，即str[u] = true，避免重复处理。
-
3. 结果输出
在主循环结束后，dis 数组中存储了从起点到每个顶点的最短距离。遍历 dis 数组，输出结果：
-
如果
dis[i]仍然是初始的大值（如0x3f3f3f3f），表示没有路径到达顶点i，输出-1。 -
否则，输出
dis[i]，表示从起点到顶点i的最短距离。
示例执行过程
假设图的结构如下：
-
顶点数
n = 5 -
边数
m = 7 -
边的权重如下：
-
1 -> 2: 4
-
1 -> 3: 3
-
2 -> 4: 2
-
3 -> 2: 1
-
3 -> 4: 5
-
4 -> 5: 1
-
2 -> 5: 7
-
初始化
-
dis数组：[0, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f] -
str数组：[false, false, false, false, false] -
g邻接矩阵：[[0x3f3f3f3f, 4, 3, 0x3f3f3f3f, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 2, 0x3f3f3f3f],[0x3f3f3f3f, 1, 0x3f3f3f3f, 5, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 1],[0x3f3f3f3f, 7, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f] ]
第1次循环
-
选择未访问的最短距离顶点：
-
遍历所有顶点，找到未访问的顶点中距离最短的顶点
u = 1（起点）。
-
-
更新邻接顶点的距离：
-
遍历顶点
1的邻接顶点2和3：-
dis[2] = min(dis[2], dis[1] + g[1][2]) = min(0x3f3f3f3f, 0 + 4) = 4 -
dis[3] = min(dis[3], dis[1] + g[1][3]) = min(0x3f3f3f3f, 0 + 3) = 3
-
-
-
标记顶点为已访问：
-
str[1] = true
-
第2次循环
-
选择未访问的最短距离顶点：
-
遍历所有顶点，找到未访问的顶点中距离最短的顶点
u = 3（dis[3] = 3）。
-
-
更新邻接顶点的距离：
-
遍历顶点
3的邻接顶点2和4：-
dis[2] = min(dis[2], dis[3] + g[3][2]) = min(4, 3 + 1) = 4 -
dis[4] = min(dis[4], dis[3] + g[3][4]) = min(0x3f3f3f3f, 3 + 5) = 8
-
-
-
标记顶点为已访问：
-
str[3] = true
-
第3次循环
-
选择未访问的最短距离顶点：
-
遍历所有顶点，找到未访问的顶点中距离最短的顶点
u = 2（dis[2] = 4）。
-
-
更新邻接顶点的距离：
-
遍历顶点
2的邻接顶点4和5：-
dis[4] = min(dis[4], dis[2] + g[2][4]) = min(8, 4 + 2) = 6 -
dis[5] = min(dis[5], dis[2] + g[2][5]) = min(0x3f3f3f3f, 4 + 7) = 11
-
-
-
标记顶点为已访问：
-
str[2] = true
-
第4次循环
-
选择未访问的最短距离顶点：
-
遍历所有顶点，找到未访问的顶点中距离最短的顶点
u = 4（dis[4] = 6）。
-
-
更新邻接顶点的距离：
-
遍历顶点
4的邻接顶点5：-
dis[5] = min(dis[5], dis[4] + g[4][5]) = min(11, 6 + 1) = 7
-
-
-
标记顶点为已访问：
-
str[4] = true
-
第5次循环
-
选择未访问的最短距离顶点：
-
遍历所有顶点，找到未访问的顶点中距离最短的顶点
u = 5（dis[5] = 7）。
-
-
更新邻接顶点的距离：
-
顶点
5没有邻接顶点，无需更新。
-
-
标记顶点为已访问：
-
str[5] = true
-
结果输出
遍历 dis 数组，输出从起点到每个顶点的最短距离：
-
dis[1] = 0 -
dis[2] = 4 -
dis[3] = 3 -
dis[4] = 6 -
dis[5] = 7
关键点总结
-
选择未访问的最短距离顶点：
-
每次选择未访问的顶点中距离最短的顶点，确保每一步都选择当前最优的顶点进行处理。
-
-
更新邻接顶点的距离：
-
通过当前顶点更新其邻接顶点的距离，确保每一步都更新到最新的最短距离。
-
-
标记顶点为已访问：
-
避免重复处理已访问的顶点，提高算法的效率。
-
-
结果输出：
-
最终输出从起点到每个顶点的最短距离，如果没有路径到达某个顶点，则输出
-1
-
