因为没学过数据结构，所以不好下手，但我也知道这是数据结构里面的东西，所以，，，还是先来学学理论吧。看了也写了测试程序，最后总结一下这个算法，当然这只是表面一点的东西，更深一点的，后面慢慢说。
Dijkstra算法
简单地说，就是先确定起点，然后搜索余下的点，记录离起点最短的点，然后呢，这个被记录的点就变成了下一次找下一个最近点的“起点”了，当然原来的距离列表就要修改了，因为你起点变了嘛，这里的起点是相对来说的，不是你给出的真正的起点，不断重得这个过程就可以找到所有的最小路径。
因为在最短路径中存在这样的事实：
设起点为 v0，而到达另一个终点 k 的有两种可能：1，v0 直接到 vk
2，v0先到 vj ,vj 到vk,当然中间可能还有更多的中间点，但原理是一样的
这样，如果v0–>vj 是最小的（如果 j == k，那就是第一种情况），那么，从 vj找到到达vk的最短距离就是v0到vk的最小距离。
这也是这个算法叫按路径长度递增次序产生 最短路径的原因！
算法用到的概念：
1.源点集合S
上面也说过，起点是相对的（这是个人的理解），对应严老师的书本，这些“起点”就组成了源点集合S，所有的点的集合为V。如此一来，每查找一次就会产生一个源点，这些源点要区别于V-S的点（就是还没有被添加到最短径中的点，在这里就是没标志的点，，下面解说）
2.始终距离列表 dist[ j ]: 这个数组表示：从源点V0(这个指的是真正的源点)出发，直接到达各个顶点（终点）的距离，如果用邻接矩阵来初始化，那么就类似如下：
dist[ j ] = adj[ v0 ][ j ];
3.源点标记数组 flag[ i ]: 用来记录哪些点已经是“起点”了，这样就不用再查找这些点了，因为这些点间的最短路径已经知道了
4.路径表 pre[ j ]: 记录路径（这里只讨论单路径的情况，即到达同一个终点的最短路径只有一种可能的情况，多种可能的后面再说，实现起来也差不多），这个数组表示：
如 pre[ j ] = m，表示，到达点 j 前要先到达点 m
好了，各个数据结构已经说明。下面是算法流程：
（1）给出起点 v0, 初始化 dist[],flag[],pre[]，三个数组，此时源点集合元素为 S = { v0 };
（2）在 V – S集合中查找离“起点”最近的点vi，并把它放进S中，此时 S = { v0, vi};
这里为什么说是“起点”，因为这个vi就是下一次循环中的起点，为什么这样说，看下面就知道。
（3）修改始终距离列表dist[j]，这个列表如何修改？按下面的原则修改：
遍历每个没有标志的顶点 k ，如果 dist[ vi ] + adj[vi][k] < dist[k],那么就dist[k] =dist[ vi ] + adj[vi][k] ，这个式子很好理解，不多说。
满足上面条件时，修改路径表：pre[ k ] = vi;就是要到达k，先到达vi
（4）重复（2）（3）共n-1次，n 是顶点数。
算法代码：
用到的一个自定义结构体：
typedef struct Graph{unsigned int vexnum;//记录顶点数，对于邻接矩阵，一定是一个方阵，所以行列相同unsigned char *vexs;//记录顶点信息int **adj;//下面注意二维数组的动态生成;}Graph;
/************************************************************************* name :search_short_path_DIJ* function: 用Dijkstra算法计算无向网G从始点v0到其余各顶点v的最短路径P[v]和其带权长度dist[v]* parameters: 1 G 图，成员adj邻接矩阵*2 v0 指定起点*3 dist 始终距离列表*4 flag 源集标志列表*5 pre 路径表* return :************************************************************************/void search_short_path_DIJ(Graph G, int v0, unsigned int dist[], BOOL flag[], int pre[]){int i,j,k,min,index;// 1 初始化各个数组for (i = 0; i < G.vexnum; ++i){pre[i] = v0;flag[i] = false;dist[i] = G.adj[v0][i];}dist[v0] = 0;flag[v0] = true;//设置S = { v0 }// 2for (i = 0; i < G.vexnum – 1; ++i){min = INFINITE;index = 0;for (j = 0; j < G.vexnum; ++j){if (!flag[j] && dist[j] < min){min = dist[j];//记录从v到各个顶点中的最小值index = j; //记录当前最小距离顶点}}//找到V-S中 dist最小的值的点，下面更新距离列表和路径表flag[index] = true;//把上面找到最小点加到S集合中// 3for (k = 0; k < G.vexnum; ++k){if (!flag[k] && (dist[index] + G.adj[index][k]) < dist[k])//这里变更了起点，变成index，因为从v出发的最短距离是先到index，注意这里查找//的点是V-S中的点{dist[k] = dist[index] + G.adj[index][k];pre[k] = index;//即到达k前，先到达index}}}//找到最短路径}下面是一个打印路径和返最小短路径的递归函数，因为pre中的点是倒过来找的，所以， 可以用栈去实现路径的打印，当然，可以用递归，在这里，个人用递归来做，因为我不想写一个栈了。。。。。。你要以乐观的态度看待这个世界，你会发现世界是如此得美好
