一千萬個為什麽

搜索

這種有向圖問題的名稱是什麽?

使用有向圖$ G $,其邊緣用自然數字裝飾。我們希望兩個頂點$ v_1 $和$ v_2 $之間的所有路徑的集合$ P $,使得路徑中的每個連續邊緣都用自然數裝飾,該自然數大於裝飾前一邊緣的自然數。

申請將是公共汽車或火車時刻表。如果您嘗試根據站點之間的轉移確定兩個城市之間的不同路線。 (在第一列火車到達之前,您不能乘坐第二列火車。)

我非正式地將其稱為“預定圖表”。但我不知道文獻中的名字是什麽。

任何與此相關的算法的引用也是有意義的。

最佳答案

據我所知,問題有時被稱為“非減少路徑”,並從50年代開始研究。 例如,參見本文:G。J. Minty。關於最短路徑問題的變體,運籌學,6(6):882-883,1958。

要求具有最小最後邊緣權重的從$ s $到$ t $的非減少路徑的問題的版本通常被稱為“最早到達”(因為最後邊緣權重是行程應用中的到達時間)。文獻中有很多關於這個版本的工作。

轉載註明原文: 這種有向圖問題的名稱是什麽?