topsorter.py 文件源码

def longestWeightedPath(self, G):
        """
        find longest path in a weighted DAG
        :param G: dag (networkx graph object)
        :return: longest_weighted_path (list)
        """
        dist = {} # stores [node, distance] pair
        # start with topological sorted order
        for node in nx.topological_sort(G):
            # pairs of dist,node for all incoming edges
            pairs = [(dist[v][0] + G[v][node]['weight'], v) for v in G.pred[node]] # incoming pairs
            if pairs:
                dist[node] = max(pairs)
            else:
                dist[node] = (0, node)
        node, (length,_)  = max(dist.items(), key=lambda x:x[1])
        path = []
        while length > 0:
            path.append(node)
            length, node = dist[node]
        return list(reversed(path))