【区别】最短路amp;amp;amp;最小生成树

一 区别
最小生成树能够保证整个拓扑图的所有路径之和最小&＃xff0c;但不能保证任意两点之间是最短路径。
最短路径是从一点出发&＃xff0c;到达目的地的路径最小。

转载

leolin_

一句话概括&＃xff1a;最小生成树是计算从一节点到另一节点的最小边集&＃xff1b;最短路是带权路径&＃xff0c;计算权值最小。也就是说&＃xff0c;最小生成树要经过每一个点&＃xff0c;而最短路只需要能达到某两点&＃xff0c;路径权值最小即可&＃xff01;

两个算法具有相当大的相似性&＃xff0c;而且都用到了贪心思想&＃xff0c;所以把他们放到一起。

【最短路】常用的算法有dijkstra&＃xff0c;bellman-ford&＃xff0c;floyd&＃xff0c;而【最小生成树】则是prim和kruskal。下面是各个算法的模板。
【Dijkstra复杂度O(n^2)】

#include //最短路
#define maxsum 0x3fffffff
int map[101][101],dist[101],s[101];
void Dijkstra(int n,int x) //n,1,递推实现
{ int mindis,u,i,j; for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) { dist[i]&＃61;map[i][x];//map[x][i] is OK&＃xff0c;dist表示i到原点的最小距离&＃xff01; s[i]&＃61;0; //printf("%d/n",dist[i]); } s[x]&＃61;1;// x&＃61;1 for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) { mindis&＃61;maxsum; u&＃61;-1; // 找出当前未使用的点j的dist[j]最小值 for(j&＃61;1;j<&＃61;n;j&＃43;&＃43;) if(s[j]&＃61;&＃61;0 && dist[j]}
int main()
{ int n,m,a,b,c,i,j; while(scanf("%d%d",&n,&m)!&＃61;EOF) { if(n&＃61;&＃61;0&&m&＃61;&＃61;0) break; for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) for(j&＃61;1;j<&＃61;n;j&＃43;&＃43;) map[i][j]&＃61;maxsum;//初始化邻接矩阵 for(i&＃61;1;i<&＃61;m;i&＃43;&＃43;) { scanf("%d%d%d",&a,&b,&c); map[a][b]&＃61;map[b][a]&＃61;c;//构造邻接矩阵,对称的&＃xff01;无向&＃xff01; } Dijkstra(n,1); printf("%d/n",dist[n]); } return 0;
}

https://blog.csdn.net/riba2534/article/details/54563524 这篇 dijkstra 讲的挺好的 还有 邻接表版

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
【最小生成树的prim模板&＃xff1a;复杂度O(n^2)】

#include//最小生成树
#define INF 0x1f1f1f1f
#define M 1000
using namespace std;
double dis[M],map[M][M];
bool flag[M];
int prim(int s,int n) //s为起点&＃xff0c;n为点的个数
{int i,j,k,temp,md,total&＃61;0;for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)dis[i]&＃61;map[s][i]; //与最短路不同&＃xff0c;而是将dis置为map[s][i]memset(flag,false,sizeof(flag));flag[s]&＃61;true; //将起点加入集合for(i&＃61;1;imap[temp][j])dis[j]&＃61;map[temp][j];}return total;
}


【Kruskal最小生成树模板  复杂度O(E*logE)】

typedef struct edge
{int a;int b;int value;
}edge;
edge edges[earraysize];
int final[narraysize]; //存储父节点 中括号里面是儿子&＃xff0c;外面是父亲
int nodecount[narraysize]; //存储该节点孩子结点的个数
bool cmp(edge a,edge b)
{return a.value}
int findp(int x) //寻找父亲
{while(x!&＃61;fa[x])x&＃61;fa[x];return x;
}
bool Union(int x,int y) //合并
{int rootx&＃61;findp(x); /*为什么要找父亲&＃xff1f;因为要判是否有回路&＃xff0c;假如父亲相同&＃xff0c;而x跟y连通&＃xff0c;那么就形成了回路*/int rooty&＃61;findp(y);if(rootx&＃61;&＃61;rooty)return false;else if(nodecount[rootx]<&＃61;nodecount[rooty]) //优化&＃xff0c;把深度小的子树加到深度大的子树&＃xff0c;减少树的高度{final[rootx]&＃61;rooty; /*其实不优化也可以直接final[rootx]&＃61;rooty或者final[rooty]&＃61;rootx也ok */nodecount[rooty]&＃43;&＃61;nodecount[rootx];}else{final[rooty]&＃61;rootx;nodecount[rootx]&＃43;&＃61;nodecount[rooty];}return true;
}
int main ()
{//freopen("a.txt","r",stdin);int num&＃61;0;int n,m;int i,j;while ( scanf ( "%d%d", &n, &m ) !&＃61; EOF ){num&＃61;0; //记录生成树中的边的数目for(i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d%d",&edges[i].a,&edges[i].b,&edges[i].value);}for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) //初始化 {final[i]&＃61;i;nodecount[i]&＃61;1;}sort(edges&＃43;1,edges&＃43;m&＃43;1,cmp); //排序 for(i&＃61;1;i<&＃61;m;i&＃43;&＃43;) //遍历所有的边 {if(Union(edges[i].a,edges[i].b)) //合并 {num&＃43;&＃43;;}if(num&＃61;&＃61;n-1) //找到了最小生成树 break;}}return 0;
}


*****************************************************************************************************************************************************************************************

*****************************************************************************************************************************************************************************************
下面是最短路的bellmen-ford算法&＃xff0c;与dijkstra不同&＃xff0c;bellman-ford可以运用于有负权值的图&＃xff0c;不过复杂度很高&＃xff0c;O(VE )... 慎用~&＃xff08;可以用SPFA&＃xff0c;它bwllman-ford的扩展&＃xff09;
Bellman-ford算法同样是对每条边进行N-1次松弛&＃xff0c;当有权值为负时&＃xff0c;对所有边进行N-1次松弛&＃xff0c;如果dis还能更新&＃xff0c;说明有负环。

ps&＃xff1a;名词解释【负环】 在一个图里每条边都有一个权值&＃xff08;有正有负)
如果存在一个环&＃xff08;从某个点出发又回到自己的路径&＃xff09;&＃xff0c;而且这个环上所有权值之和是负数&＃xff0c;那这就是一个负权环&＃xff0c;也叫负权回路
存在负权回路的图是不能求两点间最短路的&＃xff0c;因为只要在负权回路上不断兜圈子&＃xff0c;所得的最短路长度可以任意小。

Bellman-ford原理&＃xff1a;

1.如果最短路存在&＃xff0c;则每个顶点最多经过一次&＃xff0c;因此不超过n-1条边&＃xff1b;

2.长度为k的路由长度为k-1的路加一条边得到&＃xff1b;

3.由最优性原理&＃xff0c;只需依次考虑长度为1&＃xff0c;2&＃xff0c;…&＃xff0c;k-1的最短路。

Bellman-ford模板&＃xff1a;

#include//最短路
#include
#define INF 0x1f1f1f1f
#define MAX 102
#define MAXM 20008int dist[MAX];struct Edge{ //边结构体定义 int u, v, w;Edge(){}Edge(int a, int b, int c):u(a), v(b), w(c){}
}edge[MAXM];int bellman_ford(int n, int m, int s) //n个点、m条边、s为起点
{memset(dist, 0x1f, sizeof(dist)); //初始化距离很大 dist[s] &＃61; 0;int i, j, u, v, f;for (i &＃61; 1; i dist[u] &＃43; edge[j].w) // 松弛操作 {dist[v] &＃61; dist[u] &＃43; edge[j].w;f &＃61; 1;}}if (!f) return 1; //如果其中一次迭代没改变&＃xff0c;停止}for(j &＃61; 0; j dist[u] &＃43; edge[j].w) //若还能松弛, 则存在负环 return -1; //存在负环返回 -1 }return 1; //没有负环返回 1
}


算法结束后dist数组已经是最短路径。

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

【SPFA模板&＃xff1a; 期望的时间复杂度O(KE)&＃xff0c; 其中K为所有顶点进队的平均次数&＃xff0c;可以证明K一般小于等于2。】

#include//最短路
#include
#include
#include
#include
using namespace std;
#define N 50001int
INF &＃61; 0x7fffffff;
int n,m;
typedef struct edge
{ int to; int w;
}edge,temp;
vector adjmap[N]; //vector实现邻接表
int d[N];
bool vis[N]; //记录顶点是否在队列中&＃xff0c;SPFA算法可以入队列多次
int cnt[N]; //记录顶点入队列次数
void SPFA()
{ queue myqueue; int i; for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i) d[i] &＃61; INF; //将除源点以外的其余点的距离设置为无穷大 memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); d[1]&＃61;0; //源点的距离为0 vis[1] &＃61; true; cnt[1]&＃43;&＃43;; //源点的入队列次数增加 myqueue.push(1); int topint; while(!myqueue.empty()) { topint &＃61; myqueue.front(); myqueue.pop(); vis[topint] &＃61; false; for(i&＃61;0;id[topint]&＃43; adjmap[topint][i].w) { d[to] &＃61; d[topint]&＃43; adjmap[topint][i].w; if(!vis[to]) { vis[to] &＃61; true; cnt[to]&＃43;&＃43;; if(cnt[to]>&＃61;n) //当一个点入队的次数>&＃61;n时就证明出现了负环。 return ; myqueue.push(to); } } } } printf("%d/n",d[n]); }
int main()
{ //freopen("a.txt","r",stdin); scanf("%d%d",&n,&m); int i; int s,e,w; edge temp; for(i&＃61;1;i>s>>e>>w; temp.to &＃61; e; temp.w &＃61; w; adjmap[s].push_back(temp); temp.to &＃61; s; adjmap[e].push_back(temp); } SPFA(); return 0;
}