滿足三角不等式的圖是否有更好的最短路徑演算法？
對於一般的圖，單源最短路徑的Dijkstra演算法可以達到
或者
的複雜度，兩兩最短路徑可以用Johnson演算法達到
的複雜度。如果對於一個滿足三角形不等式的圖，這個複雜度是否能改進？
似乎做不到
考慮把一個滿足你所說要求的圖，每個點用一個環代替，還是滿足這個要求，但是相當於這個條件沒意義了？簡單地說就是不給任何強聯通分量。
但是可能會影響複雜度上界？在定點為平面上的點且邊的權重與頂點歐幾里得距離成正比的圖中，對Dijkstra演算法進行小的改動可以大幅提高運行速度。
在加權無環圖中，有演算法可以在線性時間內解決最短路徑問題。
等等，今天數學課上老師告訴我"最短距離"這個東西是度量，滿足三角不等式。
更新：好像可以？
先算單源最少步數，O(E)
然後按照步數分層。
把每個三角形想像成一個低一層的加上兩個高一層的，或三個同一層。這樣同一層間不存在最短路更新。
隨後從第一層推進到最後一層。O(E)。這時候最後一層的最短路已經確定。隨後從最後一層推回第一層。每多推一層，這一層的最短路都會確定。回到第一層，所有最短路確定。
O(E)。更新：這樣不行，末端的最短路的值會傳遞。
不過稍微搞搞可以把最後一層的最短路先定下來再平推回去。
適用範圍：
超大圖，e/v 小於小於v所以log(e)不科學的情況。。。不是很確定，感覺不行。對於滿足三角形不等式的圖，兩個三角可以拼成一個大三角（中間兩個邊看成一個），例如邊為1,2,100,100,對角為2的四邊形，將2和100合併成一個邊，大三角型為102,1,100不滿足三角不等式，說明這兩類問題似乎是可以轉換的。不知道這麼想是否正確。
我想問的是……為什麼平面圖會有三角不等式？平面圖是指邊集可平面化而兩兩不相交的圖，而不是在平面上散點，再用歐幾里得距離代邊權的圖……所以題主是想問平面圖，還是滿足三角不等式的圖……
推薦閱讀：
