計算的曲線圖的關鍵路徑

Question

爲圖論的作業，我要求來計算（多個）Critical (s) Routes (s)和下面的格式下的定時的一個項目的鬆弛：

項： 輸入的第一行就會一個整數C，表示測試用例的數量（建模項目活動的圖形）。每個測試用例的第一行分別包含兩個整數N和M，其中N代表項目中節點的數量和活動的數量M.然後來到m行，每行有3個整數I，J和D，其中I和J表示活動的開始和結束節點。

該條目應從位於 程序文件夾中的文件「entrada.in」中讀取。如果您的程序提供了通過圖形界面從任何路徑讀取文件 （即，沒有 寫完整路徑）的機會，將被視爲獎金。

輸出：

在每個測試用例必須顯示以下字符串「方案G：持續時間總P」的第一行，其中G表示測試用例（從1開始）和P中的總項目的數目持續時間。然後按照與輸入相同的格式（除了表示持續時間的整數除外），對項目的（多個）關鍵路線（s）應表達活動的X行，但此外，邊是排序（因爲第一優先級應該是從低端到高端節點以及從第二低端到高端的節點）。然後必須按照上面列出的相同順序遵循對應於非關鍵活動的「Y」行。對於每個非關鍵活動應該顯示4個整數，I，J，T和F，其中T和F分別表示每個活動的總鬆弛和自由鬆弛。另外，如果活動標有紅色標誌，則必須在該行的末尾添加一個R.應該避免虛擬活動不是輸出關鍵路徑的一部分。

每個測試用例應打印一個空行。 輸出應該在文件中寫入「salida.out。」

例子：

我要告訴我怎麼做我需要什麼了，我不要求一個公正的解決方案有點幫助（例如僞代碼），感謝所有

Answer 1

首先，我假設我們有一個有向無環圖（DAG）。

1 - 我們需要爲每個頂點找到每個活動的最小可能開始時間。這就像尋找圖中每個頂點的最長路徑。對於一般圖而言，這是NP-hard，但由於該圖是DAG，我們可以使用拓撲排序在多項式時間內完成此操作。

2 - 計算每個頂點的indegree（即，計算進入它們的邊的數量）。由於該圖是非循環的，至少有一個頂點的indegree爲零。將所有這些頂點放在隊列中。另外，初始化距離的陣列爲0

僞代碼

# Compute the indegree 
for each vertex v from the graph: 
    for each neighbor u of v: 
     indegree[u] += 1 

queue Q = empty queue 
distance = array filled with zeroes 
for each vertex v: 
    if indegree[v] = 0: 
     insert v on Q 

3 - 選擇從隊列的第一個頂點v。對於v的每個鄰居u，將距離[u]更新爲距離[u] = max（距離[u]，距離[v] +時間（v，u）），其中時間（v，u）執行任務（u，v）。從圖中刪除V.這可以做我減少其鄰居的indegree。排隊現在有0個indegree的新頂點。重複此過程，直到處理完所有頂點。

僞代碼

while Q is not empty: 
    v = get front element from Q 
    for each neighbor u of v: 
     distance[u] = max(distance[u], distance[v] + time(v, u)) 
     indegree[u] -= 1 
     if indegree[u] = 0: 
      insert u on Q 

4 - 現在，選擇具有最大的距離頂點X。這是項目總時間的最小值。

5 - 我們需要重新構建關鍵路徑。如果時間緊的話，任務（u，v）處於關鍵路徑上，即距離[u] +時間（u，v）=距離[v]。因此，從頂點x開始，搜索到起始頂點的路徑，並使用以下約束：如果您在頂點a中，則只能到頂點b，並且有一個邊（b，a），使得距離[a] =距離[b] +時間（b，a）。

6 - 對於不在路徑上的邊緣，您需要查找總鬆弛和自由鬆弛。自由鬆弛很容易：爲了不延遲以下任務，您需要計算下一個任務開始到當前結束時間之間的時間量。這可以通過每個（u，v）的等式：距離[v] - （距離[u] +時間（u，v））來找到。

7 - 要找到總體鬆弛情況，您需要一個新的信息，即任務可以在不延遲整個項目的情況下開始的最新時間。這可以通過恢復圖形邊緣的方向來完成。然後，從頂點x開始，使用總項目持續時間對數組進行初始化。你可以做遲到[u] = min（late [u]，late [v] - time（v，u），這樣就可以使用拓撲順序，每當你爲其所有鄰居u出列一個頂點v時， ））。在恢復方向bacj後，很容易看出每個邊（u，v）的總延遲由遲[v] - （晚[u] +時間（u，v））給出。最後，據我所知，你必須用一個R來標記所有邊緣的總鬆弛>自由鬆弛。