之前一直觉得Prim和Dijkstra很相似，但是没有仔细对比；
今天看了下，主要有以下几点：
1：
Prim是计算最小生成树的算法，比如为N个村庄修路，怎么修花销最少。
Dijkstra是计算最短路径的算法，比如从a村庄走到其他任意村庄的距离。
2：
Prim算法中有一个统计总len的变量，每次都要把到下一点的距离加到len中；
Dijkstra算法中却没有，只需要把到下一点的距离加到cls数组中即可；
3：
Prim算法的更新操作更新的cls是已访问集合到未访问集合中各点的距离；
23 for (j=0;j<n;j++)
24 {
25 if (!visited[j] && map[j][nid]<adjset[j])//更新条件：j点未访问，加入新点后已访问集合到j的距离变小了
26 {
27 adjset[j] = map[j][nid];
28 }
29 }
Dijkstra算法的更新操作更新的cls是源点到未访问集合中各点的距离，已经访问过的相当于已经找到源点到它的最短距离了；
20 for (j=1;j<=n;j++)
21 {
22 if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<cls[j])//更新条件：j点未访问，新点与j点之间有路，
23 cls[j]=cls[nxt]+map[nxt][j];
24 }
Prim算法
//初始化memset(visited,0,sizeof(visited));visited[0] = 1;len = 0;for (i=0;i<n;i++) adjset[i] = map[i][0];//Beginfor (i=1;i<n;i++){//找到下一条符合条件的点nlen = MAX;for (j=0;j<n;j++){if (!visited[j] && adjset[j]<nlen){nlen = adjset[j];nid = j;}}//访问找到的那个点len += nlen;visited[nid] = 1;//更新邻接距离for (j=0;j<n;j++){if (!visited[j] && map[j][nid]<adjset[j]){adjset[j] = map[j][nid];}}Dijkstra算法
# include <stdio.h>const MAX=0xffffffvoid Dijkstra(int v)
{int i,j,min,nxt;for(i=1;i<=n;i++) cls[i]=map[v][i]; //保存v到个点的距离memset(vis,0,sizeof(vis));vis[v]=1; //将v点访问置1for (i=1;i<n;i++){min=MAX; //min=0xffffff 无穷大nxt=v; for (j=1;j<=n;j++){if(!vis[j]&&cls[j]<min) //取未访问点到v的最小值{nxt=j;min=cls[j]; }}vis[nxt]=1; //将最小值点访问置1for (j=1;j<=n;j++) //通过nxt点将从该点经过的最短路径保存在 cls中{if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<cls[j]) cls[j]=cls[nxt]+map[nxt][j];}}
}