⑴ 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)
{