所以我的问题是我有一个非负边长的有向图G,我希望找到两个节点u和v之间的最短路径,这样它们只能通过图中的一个标记节点.
如果我们没有涉及标记节点的条件,则可以使用Dijkstra算法轻松解决该问题.
procedure dijkstra(G, l, s)
Input: Graph G = (V, E), directed or undirected;
positive edge lengths {le : e ? E}; vertex s ? V
Output: For all vertices u reachable from s, dist(u) is set to the distance from s to u.
for all u ? V :
dist(u) = ?
prev(u) = nil
dist(s) = 0
H = makequeue(V ) (using dist-values as keys)
while H is not empty:
u = deletemin(H)
for all …我想知道是否有人可以指向线性时间算法,以便在存在少量权重时找到图形的MST(即边缘只能有2个不同的权重).
除了Prim's,Kruskal's,Boruvka之外,我在google上找不到任何东西,其中似乎没有任何属性会减少这种特殊情况下的运行时间.我猜它是线性时间,它必须是对BFS的某种修改(当权重均匀时找到MST).