6

我有一个有向无环图，其中每个顶点的权重 >= 0。有一个顶点是图的“开始”，另一个顶点是图的“结束”。这个想法是找到从开始到结束的路径，其顶点的权重之和更大。例如，我有下一张图：

I(0) -> V1(3) -> F(0)
I(0) -> V1(3) -> V2(1) -> F(0)
I(0) -> V3(0.5) -> V2(1) -> F(0)

成本最高的路径是 I(0) -> V1(3) -> V2(1) -> F(0)，成本为 4。

现在，我正在使用 BFS 来枚举从 I 到 F 的每条路径，如上例所示，然后，我选择总和最大的路径。恐怕这种方法真的很幼稚。

有没有更好的算法来做到这一点？这个问题可以简化为另一个问题吗？

4

3 回答 3

4

由于您的图没有循环*，您可以否定边的权重，并运行Bellman-Ford 算法。

* Floyd-Warshall和 Bellman-Ford等最短路径算法不适用于负循环图，因为您可以通过停留在负循环中来构建任意小权重的路径。

于 2013-06-14T13:50:44.260 回答
3

您可以执行拓扑排序，然后遍历拓扑排序返回的顶点列表，从开始顶点到结束顶点并计算成本。对于当前顶点的每个有向边，检查是否可以提高目标顶点的成本，然后移动到下一个。最后 cost[end_vertex] 将包含结果。

class grph:
    def __init__(self):
        self.no_nodes = 0
        self.a = []

    def build(self, path):

        file = open(path, "r")
        package = file.readline()
        self.no_nodes = int(package[0])

        self.a = []
        for i in range(self.no_nodes):
            self.a.append([10000] * self.no_nodes)

        for line in file:
            package = line.split(' ')
            source = int(package[0])
            target = int(package[1])
            cost = int(package[2])

            self.a[source][target] = cost

        file.close()


def tarjan(graph):
    visited = [0] * graph.no_nodes
    path = []

    for i in range(graph.no_nodes):
        if visited[i] == 0:
            if not dfs(graph, visited, path, i):
                return []
    return path[::-1]


def dfs(graph, visited, path, start):
    visited[start] = 1
    for i in range(graph.no_nodes):
        if graph.a[start][i] != 10000:
            if visited[i] == 1:
                return False
            elif visited[i] == 0:
                visited[i] = 1
                if not dfs(graph, visited, path, i):
                    return False
    visited[start] = 2
    path.append(start)
    return True


def lw(graph, start, end):

    topological_sort = tarjan(graph)
    costs = [0] * graph.no_nodes

    i = 0
    while i < len(topological_sort) and topological_sort[i] != start:
        i += 1

    while i < len(topological_sort) and topological_sort[i] != end:

        vertex = topological_sort[i]

        for destination in range(graph.no_nodes):

            if graph.a[vertex][destination] != 10000:

                new_cost = costs[vertex] + graph.a[vertex][destination]
                if new_cost > costs[destination]:
                    costs[destination] = new_cost

        i += 1

    return costs[end]

输入文件：

6
0 1 6
1 2 2
3 0 10
1 4 4
2 5 9
4 2 2
0 2 10
于 2018-05-16T20:23:26.500 回答
1

一般来说，最长路径问题是 NP-hard，但由于图是 DAG，因此可以通过首先否定权重然后做最短路径来解决。见这里。

因为权重驻留在顶点上，所以在计算之前，您可能希望将权重移动到顶点的边缘。

于 2013-06-14T13:49:55.010 回答