带权图分为有向和无向，无向图的最短路径又叫做最小生成树，有prime算法和kruskal算法；有向图的最短路径算法有dijkstra算法和floyd算法。
最小生成树问题：给定一个连通无向图，寻找一颗无环树，使得树上所有边权值之和最小。
最小生成树的贪心策略的通用方法
问题描述
已知：连通无向图\(G=(V,E)\)，权重函数\(w:E \rightarrow R\) 循环不变式：在每边循环之前，A是某颗最小生成树的一个子集。 伪代码
GENERIC-MST(G,w)
A={}
while A does not form a spanning tree // 当A不是一个生成树时
find an edge(u,v) that is safe for A // 找到一条A的安全边
A = A ∪ {(u,v)}
return A注：安全边是指加入A后，不会使得A违反循环不变式。即 A ∪ {(u,v)}也是某颗最小生成树的一个子集
问题：如何寻找安全边
求安全边
定理：设A是图G的某最小生成树的一个子集。设（S,V-S）是图G中尊重集合A的任意一个切割，又设(u,v)是横跨切割(S,V-S)的一条轻量级边，则边(u,v)对于集合A是安全的。
切割：图中的线 切割尊重集合A：集合A中不存在横跨切割的边（如图a中的灰粗线构成的集合） 轻量级边：横跨一个切割的所有边中权重最小的边（不唯一）。
Kruskal和Prim关系
| term | 集合A | 说明 | 共性 |
|---|---|---|---|
| Kruskal | 森林 | 结点是原图结点，安全边是权重最小的连接两个不同分量的边 | 都是用具体的规则来确定安全边的方法 |
| Prim | 树 | 安全边是连接A和A之外某个节点的边中权重最小的边 |
Kruskal算法
寻找安全边:在所有连接两个不同树的边里，找到权重最小的边(u,v)
伪代码
MST-KRUSKAL(G,w)
A={}//A是森林
for each vertex v∈G.V
MAKE-SET(v)//将集合A初始化为空集，并创建M颗子树，每棵树各含一个结点
sort the edges of G.E into nondecreasing order by weight w //对边按照权重排序
for each edge(u,v)∈G.E,taken in nondecreasing order by weight//按权重顺序遍历边
if FIND-SET(v)!=FIND-SET(u)//(u,v)不在一棵树
A= A ∪ {(u,v)}
UNION(u,v)
return A时间复杂度
\(O(ElgV)\)
特点
图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间.
c++实现（写的很好，一定要看）:Kruskal算法
Prim算法
寻找安全边:A总是一颗树。从单一顶点开始，逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
为了快速选择新边， 在算法执行的过程中，所有不在树A中的结点都存放在一个基于key属性的最小优先队列Q中。
u.key : 连接结点u和树中结点的所有边中最小边的权重。 u.π：u在树中的父节点
描述
输入:连通图G,边权w,最小生成树的根节点r
初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}
循环：重复以下操作，直到\(V_{new}=V\)：
- 在集合E中选取权值最小的边（u,v），其中u是集合Vnew中的元素，而v则是V中没有加入Vnew的顶点；
- 将v加入Vnew中，将(u,v)加入Enew中；
输出：使用集合Vnew和Enew来描述所得到的最小生成树。
图例：
伪代码
MST-PRIM(G,w,r)//r是最小生成树的根节点
for each u∈G.V
u.key=∞
u.π=NIL //u在树中的父节点
r.key=0
Q=G.V
while Q!={}
u=EXTRACT-MIN(Q)//某条横跨切割(V-Q,Q)的一个轻量级边的端点
for each v∈G.Adj[u]//遍历u的邻接表
if v∈Q and w(u,v)<v.key
v.π=u
v.key=w(u,v)时间复杂度
通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V2）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(E log V)，其中E为连通图的边数，V为顶点数。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E + V log V)，这在连通图足够密集时（当E满足Ω（V log V）条件时），可较显著地提高运行速度