求最短路径的dijkstra算法
最短路径dijkstra算法如下：Dijkstra迪杰斯特拉是一种处理单源点的最短路径算法,就是说求从某一个节点到其他所有节点的最短路径就是Dijkstra。资料拓展：迪杰斯特拉算法(Dijkstra)是由荷兰数腔计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其薯纳衫余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。将T中顶点按递增的次序加入到S中，保证：从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度。每个顶点对应一个距离值。S中顶点：从V0到此顶点的长度。T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。初始时令S={V0},T=V-S={其余顶点}，T中顶点对应的距离值。若茄搭存在，d(V0,Vi)为弧上的权值。若不存在，d(V0,Vi)为∞。从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中。对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值。重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止。
Dijkstra算法求单源最短路
dijkstra算法用于求解单源最短路问题，只能求解正权图，图中有负边求出来的结果会有问题。 算法的思想就是先确定一个起点（源点），然后寻找这个点到其他所有点的距离最小值，找到一条距离最短的线路。 第一次查询这条路径一定是只有这两个点的，确定了这个点，就标记一下，说明这个已经是最短的了，接下来这个点就不参与比较了。 标记过后就把这个点延伸出去的边处理下，因为还要去选从起点到其他点的最短距离，所以要借助这个点去更新一下其他点的最小距离。因为第一次查询时只存储了与源点直连的点，有的点没有与源点直接连接，现在就可以借助这个确定的点进行间接连接。然后把其他直接连接的距离处理更新下。然后重复进行找距离源点最近的点，然后进行更新标记。 每一次循环会标记一个点，所以循环n次就能把n个点的图处理完毕。 第一行包含整数 n 和 m 。 接下来 m 行每行包含三个整数 x , y , z ，表示存在一条从点 x 到点 y 的有向边，边长为 z 。 求解从点1到点n 的最短路径。 堆优化版要用邻接表（链式前向星）进行存图，如果是稠密图推荐用邻接矩阵存图用朴素做法。 堆优化版在算法竞赛中比较适用，可以大幅提高运行效率。 优化思路: 因为每次循环都要去找下一个距离源点最近的的点，但是朴素做法每次都要把所有点都比较判断下，如果每次当有新的距离更新了，就把这个距离装到堆中，那么就不用再去一个个比较了，直接把堆顶元素取出就行了。 dist数组存储的是从源点到其他n个点的距离，每次找的也是这个距离，一次更新一个点，更新完毕就是起点到n个点之间的最短路。
