1.Dijkstra算法基础：
算法过程比prim算法稍微多一点步骤，但思想确实巧妙也是贪心，目的是求某个源点到目的点的最短距离，总的来说dijkstra也就是求某个源点到目的点的最短路，求解的过程也就是求源点到整个图的最短，次短距，第三短距离等（这些距离都是源点到某个点的最短距离）。。。求出的每个距离都对应一个点，也就是要到的到这个点，求的也就是原点到所有点的最短距离，并存在二维数组中，给出目的点就能直接通过查表获得最短距离。
第1步：以源点START(假设s1)为始点，求最短距离，如何求? 与这个源点相邻的点与源点的距离全部放在一个数组dist[]中，如不可达，dist[]中为最大值，是一维数组原因是默认的是从源点到这个一维数组下标的值，只需目的点作为下标就可，这时从源点到其他点的最短的“1”条路径有了，只要选出dist[]最小的就行（得到最短路径的另一端点假设s2）。
第2步：这时要寻找源点(设s1)到另外点的次短距离，按路径长度递增次序产生各顶点最短路径，这个距离是dist[]里的值或是从第1步中选择的那个最短距离+从找到点(设s2)出发到其他点的距离（其实这里是一个更新操作更新的是dist[]里的值），如最短距离+从这点（设s2）到其他点的距离小于dist[]里面的值，就可更新dist[]数组，然后再从dist[]中选值最小的，也就是第“2”短路径（次短路径）。
第3步：寻找第“3”短路径，同上，第二短路径的端点（s3）更新与之相邻其他的点的dist[]数组里面的值。
第4步：重复上述过程n - 1次（n节点个数），得出结果，其实把源点到所有点的最短路径求出来了，都填在了dist[]表中，要找源点到哪个点的最短路，就只需要查表了。
在未选点集中选择一个最短距离最小的未选点k来扩充已选集是Dijkstra算法的关键。时间复杂度O(n^2).
1 void Init_Dijkstra(void) 2 { 3 count=0; 4 for(int i=0;i<MG->n;i++) 5 { 6 vis[i]=0; //状态置0,表示没有求出最短路径 7 min_wg[i]=MG->edge[START][i]; 8 9 if(min_wg[i] == INF) 10 min_from[i]=-1; //表示到顶点i路径最短的上一个顶点不存在 11 else 12 min_from[i]=START; 13 } 14 15 vis[START]=1; 16 count++; 17 min_wg[START]=0; //从源点到达源点的边权值为0 18 min_from[START]=START; //源点的父节点为本身 19 } 20 21 void Dijkstra(void) 22 { 23 int min,to_index; 24 int new_dis; //距离更新中间值 25 26 while(count < MG->n) 27 { 28 min=INF; 29 to_index=-1; 30 for(int i=0;i<MG->n;i++) 31 if(!vis[i] && (min_wg[i] < min)) 32 { 33 min=min_wg[i]; 34 to_index=i; 35 } 36 37 if(to_index != -1) 38 { 39 // if(to_index == ENDN) //用于[2] 40 // break; 41 vis[to_index]=1; 42 count++; 43 } 44 else 45 break; 46 47 for(int j=0;j<MG->n;j++) 48 if(!vis[j] && MG->edge[to_index][j] < INF) 49 { 50 new_dis=min_wg[to_index]+MG->edge[to_index][j]; 51 if(new_dis < min_wg[j]) 52 { 53 min_wg[j]=new_dis; 54 min_from[j]=to_index; 55 } 56 } 57 } 58 }