查找從s中的曲線圖的最短路徑來考慮下面的問題的所有頂點

Question

：用加權函數w

鑑於向圖G =（V，E）表示：V→R，描述了一種算法 找到從S到所有其他頂點的最短路徑，其中 路徑的長度等於所有頂點的總和。您需要更改現有算法 以使其工作，因此無需編寫新算法。

請注意，權重函數位於頂點而非邊（!!）。 我當時的想法是改變Bellman-Ford算法，改變放鬆檢查以下內容：

1.if d[v]>d[u]+w[u] 
1.1 d[v] <<-- d[u]+w[u] 
1.2 PI[v] <<-- u 

我並不想這樣的作品足夠好，任何想法可能是什麼問題？

感謝，羅恩

Answer 1

讓w:V->R是你的體重的功能。

創建增重功能：w':E->R如下：w'(u,v) = w(v)

運行的Dijkstra /貝爾曼 - 福特與W」。根據w'，令d'[v]是最小路徑對v的權重。

然後，如果最短路徑是s->u1->u2->...->un->v，您可以：d'[v] = w'(s,u1) + w'(u1,u2) + ... + w'(un,v) [由Dijkstra算法/貝爾曼fofrd的正確性]，從而d'[v] = w(u1) + w(u2) + ... + w(un) + w(v) [由W'的定義。

所以，總體上得到：d[v] = w(s) d'[v]和d [v]是頂點的最短路徑。

Answer 2

我認爲Floyd–Warshall_algorithm是最好的起點。當然，維基百科今天抗議了:)。