把距離取負值就是個最短路徑問題，有負權值的最短路徑不適用dijkstra演算法，但基於鬆弛技術的bellmanford和floyd演算法都是適用的，計算多點之間最短路徑使用floyd演算法，具體來說是進行n-2輪鬆弛，即對任意兩點窮舉第三點，並嘗試將距離替換成經由第三點的距離。完成後額外進行一輪鬆弛，如果距離繼續變小，說明存在負權有向環，最短路徑不存在（可以不斷沿著環繞），否則當前路徑就是最短路徑。不過看題主的意思，這個圖有一個特殊特性，它的有向邊只能從編號小的通往編號大的，這就更簡單一些了，以某個點結束的路徑只能由編號比它小的頂點及這些頂點之間的邊決定，這是個動態規劃問題。可以如下表述：其中D[k]為以頂點k結尾的最長路徑的長度，d(j,k)表示j和k之間有向邊的距離。如果用特殊的鄰接表（反向的鄰接表，邊按照終點組織）來表示圖，這是個O(E)複雜度的演算法，最後要求的答案就是D[k]的最大值。