Prim算法和Dijkstra算法的异同

之前一直觉得Prim和Dijkstra很相似，但是没有仔细对比；

今天看了下，主要有以下几点：

1：

Prim是计算最小生成树的算法，比如为N个村庄修路，怎么修花销最少。

Dijkstra是计算最短路径的算法，比如从a村庄走到其他任意村庄的距离。

2：

Prim算法中有一个统计总len的变量，每次都要把到下一点的距离加到len中；

Dijkstra算法中却没有，只需要把到下一点的距离加到dist数组中即可；

3：

Prim算法的更新操作更新的dist是已访问集合到未访问集合中各点的距离；

1 for (j=0;j<n;j++)
2 {
3     if (!visited[j] && map[j][pos]<dist[j])//更新条件：j点未访问，加入新点后已访问集合到j的距离变小了
4     {
5         dist[j] = map[j][pos];
6     }
7 }

Dijkstra算法的更新操作更新的dist是源点到未访问集合中各点的距离，已经访问过的相当于已经找到源点到它的最短距离了；

1 for (j=1;j<=n;j++)
2 { 
3     if(!visited[j]&&&&(dist[u]+map[u][j])<dist[j])//更新条件：j点未访问，新点与j点之间有路，
4     dist[j]=dist[u]+map[u][j];//u为寻找的下一个节点 
5 }

Prim算法：

 1 memset(visited,0,sizeof(visited));//初始化
 2 visited[0] = 1;
 3 len = 0;
 4 for (i=0;i<n;i++)    
 5 dist[i] = map[0][i];//Begin
 6 for (i=1;i<n;i++)
 7 {
 8     //找到下一条符合条件的点
 9     min = MAX;
10     for (j=0;j<n;j++)
11     {
12         if (!visited[j] && dist[j]<min)
13         {
14             min = dist[j];
15             pos = j;
16         }
17     }
18     //访问找到的那个点
19     len += min;
20     visited[pos] = 1;
21     //更新邻接距离
22     for (j=0;j<n;j++)
23     {
24         if (!visited[j] && map[pos][j]<dist[j])
25         {
26             dist[j] = map[pos][j];
27         }
28     }
29 }

Dijkstra算法：

 1 void Dijkstra(int v)
 2 {
 3     int i,j,min,u;
 4     for(i=1;i<=n;i++)    
 5     dist[i]=map[v][i];
 6     memset(vis,0,sizeof(vis));
 7     vis[v]=1;
 8     for (i=1;i<n;i++)
 9     {
10         min=MAX;
11         u=v;
12         for (j=1;j<=n;j++)
13         {
14             if(!vis[j]&&dist[j]<min)
15             {
16                 u=j;
17                 min=dist[j];
18             }
19         }
20         vis[u]=1;
21         for (j=1;j<=n;j++)
22         {
23             if(!vis[j]&&(dist[u]+map[u][j])<dist[j])
24                 dist[j]=dist[u]+map[u][j];
25         }
26     }
27 }