嗨,所有图论专家:)
我目前面临一个我自己无法解决的算法问题。
我必须在已经包含直接股份的有向图中找到每家公司的所有间接股份(参见图像以获得一个非常简单的示例)。
我必须从一个有向图开始,其中节点是公司,边是这些公司之间的直接股份。该算法现在必须将所有节点之间的间接份额附加到边上(这包括在算法期间向图中添加新边)。
间接份额定义为所有中间直接份额的乘积。如果图中只有节点 A、B 和 C,则只有一个间接份额,即从 A 到 C 的份额。
间接(A,C)= 100% * 80% = 1 * 0.8 = 0.8 = 80%
现在我需要一个算法来计算整个图表的这些份额。图中没有特定的起点,它可能包含各种大小的圆(在示例中,C 和 D 之间只有一个“直接”圆)和一对节点之间的多条路径(如路径从 C 到 E)。
如果有人可以帮助我提供一些伪代码或可能算法的描述,那将非常有帮助。我已经在图论书籍和互联网上搜索了算法,但我能找到的都是用于查找最短路径、所有路径或访问图的所有节点的标准算法。但是我找不到一种机制来计算这种图边权重的数学组合。