之前一直觉得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算法
1 //初始化 2 memset(visited,0,sizeof(visited)); 3 visited[0] = 1; 4 len = 0; 5 for (i=0;i<n;i++) adjset[i] = map[i][0]; 6 //Begin 7 for (i=1;i<n;i++) 8 { 9 //找到下一条符合条件的点 10 nlen = MAX; 11 for (j=0;j<n;j++) 12 { 13 if (!visited[j] && adjset[j]<nlen) 14 { 15 nlen = adjset[j]; 16 nid = j; 17 } 18 } 19 //访问找到的那个点 20 len += nlen; 21 visited[nid] = 1; 22 //更新邻接距离 23 for (j=0;j<n;j++) 24 { 25 if (!visited[j] && map[j][nid]<adjset[j]) 26 { 27 adjset[j] = map[j][nid]; 28 } 29 }Dijkstra算法
1 void Dijkstra(int v) 2 { 3 int i,j,min,nxt; 4 for(i=1;i<=n;i++) cls[i]=map[v][i]; 5 memset(vis,0,sizeof(vis)); 6 vis[v]=1; 7 for (i=1;i<n;i++) 8 { 9 min=MAX; 10 nxt=v; 11 for (j=1;j<=n;j++) 12 { 13 if(!vis[j]&&cls[j]<min) 14 { 15 nxt=j; 16 min=cls[j]; 17 } 18 } 19 vis[nxt]=1; 20 for (j=1;j<=n;j++) 21 { 22 if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<cls[j]) 23 cls[j]=cls[nxt]+map[nxt][j]; 24 } 25 } 26 }
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/10/09/2717106.html
相关资源：数据结构—成绩单生成器