dijkstra更新的时候是选中不在s中距离最小的点t 用t来更新所有点到起点的一个距离
prim更新时是选中不在s中距离最小的点t 用t来更新所有点到集合的一个距离
dijkstra迭代n-1次 初始是已经选中了dist[1] = 0 所以只有n-1个点需要迭代
prim迭代n次 初始没有选中任何点 所以n个点需要迭代
不存在生成树:所有点不连通
if(i && dist[t] == INF)含义:
当前距离最近的点到集合的距离都是正无穷(不连通)
if(i) ans += dist[t] 含义:
只要不是第一个点 , 就把答案加上
dijkstra :dist[j] = min(dist[j] , dist[t] + g[t][j]); // 指的是点1到点t的最短距离加上t到j的边的距离
prim : dist[j] = min(dist[j] , g[t][j]); // 表示这个点j到集合s里的点t的距离 如果有连边的话 看下边的长度
注意点:
if(i) ans += dist[t];
for(int j = 1 ; j <= n ; j ++ ) dist[j] = min(dist[j] , g[t][j]);
这两句话不能够调换 原因如下:
若点t有自环 , 若把语句调换 , dist[t] 会被更新成更小
比如说dist[t] = -9 ,g[t][t] = -19 ; 先执行更新语句会把dist[t]更新成-19
但是最小生成树是不允许有自环的
区别在于dist数组的含义不同,导致的循环次数上的不同。相同点是都可以自己处理自环,我们只需要处理重边即可
好滴