⑴ Dijkstra算法
迪杰斯特拉算法（Dijkstra）是由荷兰计算机科学家狄克斯特拉在1959年提出的。它是一种求解有权图中最短路径的算法，主要特点是采用贪心算法的策略，从起始点开始，每次遍历到距离始点最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
迪杰斯特拉算法求的是单源最短路问题。其实现过程如下：
示例中我们可以发现，这里的迪杰斯特拉算法只适用于边权均为正的图。Dijkstra模板题如下：
给定一个有n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。输入格式：第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。输出格式：输出一个整数，表示1号点到n号点的最短距离。如果路径不存在，则输出-1。数据范围：[公式]，[公式]，图中涉及边长均不超过10000。输入样例：3 3 1 2 2 2 3 1 1 3 4 输出样例：3
分析：由本题的点和边的数据范围可知，这是一个稠密图，因此使用邻接矩阵来存储图。（朴素Dijkstra正是用来处理稠密图的）注意：本题有重边和自环。由于边权为正，所以自环一定不会在最短路中。而对于重边，我们存下最短边即可。
代码实现：时间复杂度为[公式]。对于稀疏图（m与n数据范围接近时），Dijkstra还有另外一种形式：堆优化Dijkstra。优化主要在寻找距离最小的点的操作上。堆有两种实现方式，之前已经有写过手写堆，这里使用另外一种堆的实现方式：优先队列。由于是稀疏图，存储方式需要改成邻接表形式。其思路和朴素Dijkstra一致。
代码实现：时间复杂度为[公式]。
以上就是朴素Dijkstra算法和堆优化Dijkstra算法。都是用于单源正权边最短路。未必优化版的就是更好的，朴素版适合稠密度，堆优化版适合稀疏图。
⑵ 简谈迪克斯特拉算法
一直想要学点简单的算法，叨叨了好久，开始吧【这篇文章的前言无非就是我想说点废话，大家可以选择性的过滤哈。】
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家 狄克斯特拉 于1959 年提出的，因此又叫 狄克斯特拉算法 。是从一个顶点到其余各顶点的 最短路径 算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
敲黑板~进入正题
迪杰斯特拉算法是目前 OIER 们最爱用的最短路算法，下面讲一下这个算法的思路【图丑，请大家忍耐一下】：
第一步，我们先把a加入集合，数组变成（s = {a}, dis[] = {0, ∞,∞,∞,∞,∞,∞,∞}）
第二步，找到和a最近的点，为b，把b加入集合，并确定他的最短路径【要注意箭头方向哈仿歼塌】，数组变成（s = {a, b}, dis[] ={0,2,∞,∞,∞,∞,∞,∞}）
第三步，找到和b最近的点，为d，把d加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d}, dis[] = {0,2,∞,3,∞,∞,∞,∞}）
第四步，找到和d最近的点，为e，把e加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e}, dis[] = {0,2,∞,3,5,∞,∞,∞改纤}）
第五步，找到和e最近的点，为f，把f加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f}, dis[] = {0,2,∞,3,5,9,∞,∞}）
第六步，找到和f最近的点，为g，把g加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f, g}, dis[] = {0,2,∞,3,5,9,12,∞}）
第七步，目前只剩下c和h了，那么我们先要找到距离集合路径最短的c，把c加备圆入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g}, dis[]= {0,2,13,3,5,9,12,∞}）
第八步，最后一步，我们找到距离集合路径最短的h，把h加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g, h}, dis[] = {0,2,13,3,5,9,12,18}）
得嘞，这个大致的思路是这样的，还有后续哟，欲知后事如何，请看下回讲解~
⑶ 狄克斯特拉算法的path是怎么算出来的
Dijkstra算法（狄克斯特拉算法） Dijkstra算法是由荷兰计算机科学家 狄克斯特拉 （ Dijk stra ）于1959 年提出的，因此又叫狄克斯特拉算法。 是从一个顶点到其余各顶点的最短路径算法， 解决的是有向图中最短路径问题。
程序如下，稍加改动即可。
带权有向图的最短路径的求解
//带权有向图的最短路径的求解
#include <stdio.h>
#include <stdlib.h>
#define MAXV 50
#define INF 32767
typedef int InfoType;
//邻接矩阵存储方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//狄克斯特拉算法
void Ppath(int path[],int i,int v)
{