在有向图中查找不同路径数的算法 [英] Algorithm to find the number of distinct paths in a directed graph

问题描述

可能的重复:
查找两个任意顶点之间所有连接的图算法

我有一个有向图，我可以使用什么算法来查找 2 个特定顶点之间不同的非循环路径的数量，并计算这些不同路径中使用任何路径的最大次数?如果两条路径访问不同数量的顶点或以不同的顺序访问顶点，则它们是不同的.

I have a directed graph, what algorithm can i use to find the number of distinct acyclic paths between 2 particular vertices, and count the maximum times any path is used in these distinct paths? Two paths are distinct if they either visit a different number of vertices or visit vertices in a different order.

推荐答案

如果您遵循稍微修改的 Dijkstra 算法，您就可以得到一个全对解决方案.

If you follow a slightly modified Dijkstra's algorithm, you can have an all-pair solution.

说明:从 u 到 v 的路径是以下内容的总和:

Explanation: Paths from u to v is the sum of the following:

1. 从u到v的不经过w
的路径
2. 通过w的路径=从u到w的路径数次从<的路径数code>w 到 v

1. Paths from u to v which doesn't pass through w
2. Paths which go through w = number of paths from u to w times number of paths from w to v

用零初始化矩阵，除非存在从 i 到 j(即 1)的边.那么下面的算法会给你结果(all-pair-path-count)

Initialise the matrix with zeros except when there is an edge from i to j (which is 1). Then the following algorithm will give you the result (all-pair-path-count)

for i = 1 to n:
    for j = 1 to n:
        for k = 1 to n:
            paths[i][i] += paths[i][k] * paths[k][j]

不用说:O(n^3)

Needless to say : O(n^3)

渴望阅读单对解决方案.:)

Eager to read a single pair solution. :)

这篇关于在有向图中查找不同路径数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！