Dijkstra的算法分析 （十万火急）

Dijkstra算法是单源最短路径问题的一种求解算法
　　问题描述：在一个无向图中，有若干个点。某些点存在路径。如何从一个点到达另一个点使走的路程最短？
　　它是运用贪心的算法不断添加点从而到达终点。建立一个集合，在代码中可以用来标记一下就可以。这个集合的初始时只有起点，我们把从源到u且中间只经过S中顶点的路程为从源到u的特殊路径，并用dist数组记录当前每个顶点所对应的最短特殊路径。Dijkstra算法从源出发，达到直接相连的点i，设为一层点，并把dist[i]赋为其权值。然后再检查与这几个点（除源点）相连的点，设为二层点，二层点中可能有一层点,比较一下源点直接到该点的路程和源点间接到达该点路程，修改dist[]，直到找到终点。
　　其中和prim算法有点相似，又和BFS有点相似。
　　void Dijkstra(int n,int v,int dist[],int prev[],int **table){
　　//其中n指n个节点,v指起点,dist[i]记录源点到i点的最短特殊路径,prev[i]记录在特殊路径当中i点的前一个点,table[][]就是无向图的邻接矩阵
　　int i,j,k;
　　bool s[maxint]; //maxint是个非常大的数
　　for (i=1;i<=n;++i)
　　{
　　dist[i] = table[v][i];
　　s[i] = false;
　　if (dist[i] == maxint) prev[i] = 0; //将该点的前一个点赋为0,应为它不与v点直接相连
　　else prev[i] = v;
　　}
　　dist[v] = 0; s[v] = true; //与prim不同的是初始时从源点出发
　　for (i=1;i<n;++i)
　　{
　　int temp = maxint;
　　int u = v;
　　for (j=1;j<=n;++j)
　　{
　　if ((!s[j])&&(dist[j]<temp))