0

我有一个这样的加权有向图：

在此处输入图像描述

我想找到从开始到结束的最大成本路径的顶点列表。

在这个例子中，我应该得到：

'enableBrowserExtension' -> 'newWindow' -> 'newTab' -> 'startPage' -> 'typed' -> 'selectTab' -> 'clickTextField' -> 'changeField-frullatore' -> 'clickButton-VAI' -> 'submit' -> 'formSubmit' -> 'mouseClick' -> 'link'

我正在尝试使用此处找到的代码：

import networkx as nx

def inverse_weight(graph, weight='weight'):
    copy_graph = graph.copy()
    for n, eds in copy_graph.adjacency():
        for ed, eattr in eds.items():
            copy_graph[n][ed][weight] = eattr[weight] * -1
    return copy_graph

def longest_path_and_length(graph, s, t, weight='weight'):
    i_w_graph = inverse_weight(graph, weight)
    path = nx.dijkstra_path(i_w_graph, s, t)
    length = nx.dijkstra_path_length(i_w_graph, s, t) * -1
    return path, length

if __name__ == '__main__':
    DG = nx.DiGraph()
    DG.add_edge('enableBrowserExtension', 'enableBrowserExtension', weight=3)
    DG.add_edge('enableBrowserExtension', 'newWindow', weight=1)
    DG.add_edge('newWindow', 'newTab', weight=1)
    DG.add_edge('newTab', 'startPage', weight=1)
    DG.add_edge('startPage', 'typed', weight=1)
    DG.add_edge('typed', 'selectTab', weight=2)
    DG.add_edge('selectTab', 'newTab', weight=1)
    DG.add_edge('newTab', 'typed', weight=1)
    DG.add_edge('typed', 'typed', weight=1)
    DG.add_edge('selectTab', 'clickTextField', weight=2)
    DG.add_edge('clickTextField', 'changeField', weight=1)
    DG.add_edge('changeField', 'clickButton', weight=1)
    DG.add_edge('clickButton', 'submit', weight=1)
    DG.add_edge('submit', 'formSubmit', weight=1)
    DG.add_edge('formSubmit', 'mouseClick', weight=1)
    DG.add_edge('mouseClick', 'link', weight=2)
    DG.add_edge('link', 'formSubmit', weight=1)
    DG.add_edge('formSubmit', 'selectTab', weight=1)
    DG.add_edge('selectTab', 'mouseClick', weight=1)
    DG.add_edge('mouseClick', 'clickLink', weight=1)
    DG.add_edge('clickLink', 'link', weight=1)
    DG.add_edge('link', 'mouseClick', weight=2)
    DG.add_edge('mouseClick', 'changeField', weight=1)
    DG.add_edge('changeField', 'mouseClick', weight=1)
    DG.add_edge('mouseClick', 'selectTab', weight=1)

    path, length = longest_path_and_length(DG, 'enableBrowserExtension', 'link')

但我得到了错误：

ValueError: ('Contradictory paths found:', 'negative weights?')

我也试过这个java代码，但它只返回整数的最大总成本，我想要路径上顶点的名称。

有没有办法来解决这个问题？

4

1 回答 1

1

由于图中有正值循环，因此最大成本路径是无限的。您需要删除琐碎的循环并巧妙地处理其他循环。也许您有一个未实现的要求，即没有节点被访问超过一次？

无限循环的各种方式是你得到“矛盾路径”的原因。

于 2020-03-12T22:26:37.493 回答