1樓：李亞韜
更新：好像可以？
先算單源最少步數，O(E)
然後按照步數分層。
把每個三角形想象成乙個低一層的加上兩個高一層的，或三個同一層。
這樣同一層間不存在最短路更新。
隨後從第一層推進到最後一層。O(E)。
這時候最後一層的最短路已經確定。
隨後從最後一層推回第一層。
每多推一層，這一層的最短路都會確定。
回到第一層，所有最短路確定。
O(E)。
更新：這樣不行，末端的最短路的值會傳遞。
不過稍微搞搞可以把最後一層的最短路先定下來再平推回去。
適用範圍：
超大圖，e/v 小於小於v所以log(e)不科學的情況。。。
2樓：
不是很確定，感覺不行。對於滿足三角形不等式的圖，兩個三角可以拼成乙個大三角（中間兩個邊看成乙個），例如邊為1,2,100,100,對角為2的四邊形，將2和100合併成乙個邊，大三角型為102,1,100不滿足三角不等式，說明這兩類問題似乎是可以轉換的。不知道這麼想是否正確。
3樓：
似乎做不到
考慮把乙個滿足你所說要求的圖，每個點用乙個環代替，還是滿足這個要求，但是相當於這個條件沒意義了？
簡單地說就是不給任何強聯通分量。
但是可能會影響複雜度上界？
4樓：
我想問的是……為什麼平面圖會有三角不等式？
平面圖是指邊集可平面化而兩兩不相交的圖，而不是在平面上散點，再用歐幾里得距離代邊權的圖……
所以題主是想問平面圖，還是滿足三角不等式的圖……
什麼是三角不等式？
已登出 三角不等式來自於這樣乙個我們日常生活的經驗 兩點之間直線段最短，或者說三角形任意兩邊之和大於第三邊。用數學語言描述，就是 d x,y d x,z d z,y 三角不等式在不同的內積空間有不同的形式，我們最熟悉的就是絕對值不等式 x y x z z y 這裡令x z a,z y b,有 a b...
點積為什麼不滿足三角不等式？
睎xii 開啟這個鏈結你自然會明白https www. 杜鑫 三角不等式是寫在度量空間和賦範空間的定義裡的，而內積空間的定義沒有三角不等式這一條。三者的對比可以參照這位答主的回答 範數空間，度量空間，內積空間有什麼關係？菊叔的回答 知乎 https www. 已登出 三角不等式是針對度量空間的，d表...
柯西不等式的證明有哪些？
TravorLZH 定理 柯西不等式 設V為數域F上的內積空間，設 則 right le u cdot v eeimg 1 證明 設 over left v eeimg 1 則有 0 eeimg 1 因此，z和v正交並且u可以被改寫為 over left v eeimg 1 再根據勾股定理，我們可以...