迪杰斯特拉算法用于计算图中最短路径

迪杰斯特拉算法专为解决单一出发点的最短路径问题而设计，在这种情况下它能够计算出从一个节点到所有其他节点的最短距离。其核心理念在于逐步扩展最近的节点以确定最优路径长度。该算法的理念与普里姆算法用于构建最小生成树的过程具有相似性。

迪杰斯特拉算法思想：

为了存储各个节点到源节点的距离关系，我们使用一个dis数组。在每次循环中找出与源节点最近的节点，并将其确定下来（被确定为最短路径的一部分后就不再参与后续计算）。随后我们对选定节点的所有相邻节点进行分析（即其相连的所有节点），并记录这些相邻节点的基本信息以及它们当前相对于源节点的距离信息。如果发现初始源节点到选定最近节点的距离加上该相邻节点相对于选定最近节点的距离小于初始源节点直接到达该相邻节点所记录的距离值，则需对相关距离进行更新计算（即更新距离数组中的对应项）。这一过程将反复执行N-1次（或N次），其中N代表图中所有独立顶点的数量。经过上述所有操作后得到的结果即为最短路径树中各目标顶点相对于起始顶点的最短路径长度分布情况。

    #include <bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f
    int dis[100],N,M,G[100][100],book[100];//dis里的数组就是源点1到各点的最短路