1-1hit |
Kunihiko ISHIMA Shuji TSUKIYAMA
In this letter, we consider the following problem: Given a weighted digraph G=[V, EaEb] such that subgraph Ga=[V, Ea] of G is an acyclic graph with a single source vertex and the weight of each edge in Eb is negative, if G has a positive cycle, then locate them as many as possible; otherwise, compute the longest path length from source vertex to each vertex of V. Then, we propose an algorithm to this problem and show some experimental results to demonstrate the efficiency of the proposed algorithm.