最短路径生成树

最短路径生成树是一棵树，它的根节点为S，在这棵树上跑dijkstra与在原图上跑得到的d会是完全一样的。
这棵树的生成可以用dijkstra来理解。每个未被标记的节点把d推priority_queue，取出堆顶x，x先被标记。
然后更新与x相连的节点，如果有d[y]>d[x]+e[k].c，那么把y节点以及k这条边一起选入预定的最小路径生成树。
当y被标记时，这条预定的边变成实际的最小路径生成树的一条边。
再理解一下，dijkstra看似随机的从priority_queue中随机的取点，实际上它取的点还是有原则的。
画一个图出来，YY一下，可以发现dijkstra的扩展路径就是一棵树，
（很满足树的特性，一个点有很多个孩子节点，每个点只有一个父亲……）把这棵树提取出来便是最小路径生成树啦

其实这个不难想到，只是他会出一些结合的题，所以还是明确一下概念比较好

这是一个求最短路径树的方案数的题

#include<bits/stdc++.h>
#define inf 1e12;
using namespace std;
int n,m,x,y,z;
long long dis[1010][1010],g[20000],cnt[20000];
bool vis[2000000]={0};
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)//一、预处理
{
if(i == j) dis[i][j]=0;
else dis[j][i] = dis[i][j] = inf;
}
for(int i = 1;i <= m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(dis[x][y] > z)
dis[x][y] = dis[y][x] = z;
}
for(int i = 1;i <= n;i++) g[i]=dis[1][i];
for(int i = 1;i <= n;i++)// 二、用迪杰斯特拉算法求出一号房间到每个房间的单源最短路
{
long long minn = inf;
int u;
for(int j = 1;j <= n;j++)
{
if(!vis[j] && minn > g[j])
{
minn = g[j];
u = j;
}
}
//最小边
vis[u] = 1;
for(int j = 1;j <= n;j++)
if(g[j] > dis[u][j] + g[u])
g[j] = g[u] + dis[u][j];
}
long long ans = 1;
for(int i = 1;i <= n;i++)//三、方案累加
for(int j = 1;j <= n;j++)
if(i != j && g[j] == g[i] + dis[i][j])
cnt[j]++;
for(int i = 1;i <= n;i++)
{
if(cnt[i] == 0) continue;
ans *= cnt[i];
ans %= 2147483647;
}
printf("%lldn",ans);
}

最后

以上就是犹豫镜子为你收集整理的最短路径生成树的全部内容，希望文章能够帮你解决最短路径生成树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。