犹豫镜子

文章
3
资源
0
加入时间
2年10月17天
最短路径生成树

最短路径生成树

最短路径生成树是一棵树，它的根节点为S，在这棵树上跑dijkstra与在原图上跑得到的d会是完全一样的。这棵树的生成可以用dijkstra来理解。每个未被标记的节点把d推priority_queue，取出堆顶x，x先被标记。然后更新与x相连的节点，如果有d[y]>d[x]+e[k].c，那么把y节点以及k这条边一起选入预定的最小路径生成树。当y被标记时，这条预定的边变成实际的最小路径生...
图论 2023-11-18

他的专栏

JavaScript（1）
C#（1）
图论（1）

他的归档

2023年11月（1）
2022年05月（1）
2022年04月（1）

热门文章

1
jquery.validate使用时遇到的问题
2
C#利用正则判断输入是否为纯数字、容器类
3
最短路径生成树