我有一个无向图,完全图,并希望将它转换成一个有向无圈图,在每个节点之间有一个(单向)路径。为了开始,我想添加随机边和停止一旦所有节点连接。需要研究的是一个算法(使用Python,但任何语言都可以)。
因此,例如,这个图不再被进一步连接:
A ---- B A ---> B
\ / => /
\ / v
C C
,但在这种情况下,所有无向边都会变成有向边。
A ---- B A ---> B
\
我一直在研究加权有向图的图算法,特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。
设G是一个具有节点{1,…,n}和邻接矩阵A的加权有向图。设B_k i,j是从i到j的最短路径,它使用中间节点<= k。
input A
if i = j then set B[i, j] = 0
set B[i, j] = 0
else if i != j && there is an arc(i, j)
set B[i, j] = A[i, j]
else
set B[i, j] = infinity
#B = B0
for k = 1 to n:
我正在尝试更好地理解Dijkstra的算法。我已经附上了我的教科书中的算法的图像。伪代码显示输入是无向图,但是算法对于有向图有什么不同吗?我已经查找了输入有向图的算法,我没有发现任何差异。
Algorithm ShortestPath(G, v)
Input: A simple undirected weighted graph G with nonnegative edge weights and a distinguished vertex v of G
Output: A label D[u], for each vertex u of G, such that D[u] is th