Prim算法和Dijkstra算法的异同

之前一直觉得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];         //Begin         for (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算法
void Dijkstra(int v){    int i,j,min,nxt;    for(i=1;i<=n;i++)    cls[i]=map[v][i];    memset(vis,0,sizeof(vis));    vis[v]=1;    for (i=1;i<n;i++)    {        min=MAX;        nxt=v;        for (j=1;j<=n;j++)        {            if(!vis[j]&&cls[j]<min)            {                nxt=j;                min=cls[j];            }        }        vis[nxt]=1;        for (j=1;j<=n;j++)        {            if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<cls[j])                cls[j]=cls[nxt]+map[nxt][j];        }    }}