1樓：程式小猿
V代表頂點數量，E代表邊的數量。
用BFS解決單源最短路徑問題，空間是和V成正比的，時間和EV成正比。
樓下的回答提到了Bellman-Ford演算法，基於佇列的這個版本演算法，就是利用的BFS，在這個過程中relax節點。
樸素的Bellman-Ford會以任意順序relax。
它們在最壞的情況下，時間和空間複雜度是一樣的。
2樓：楊個毛
不管是深搜，廣搜，雙向廣搜，你都需要乙個陣列記錄每個節點你是否訪問過（1 bit * n），然後你需要乙個資料結構來記錄待處理節點（乙個棧，乙個佇列或者兩個佇列），後面這個資料結構的大小上限總是sizeof(index) * n的。所以並沒有區別。
而且等等，這幾個演算法都不是拿來解決最短路的吧……除非你說的是不帶權的版本。既然你提到的都是這幾個演算法，我就預設如此了。不是的話，請談論Dijkstra/Bellman-ford而不是這三個演算法。
說ID-DFS的匿名使用者，如果你ID的同時還想堅持多項式時間複雜度的話，還是需要上述兩個資料結構；如果你多項式都不要了的話，第乙個資料結構可以省掉，第二個仍然省不掉，然而O(sizeof(index)*n)和O((1+sizeof(index))*n)顯然是同乙個東西，就算精確到bit也沒有多少有意義的差距，32位機的話兩個東西只差了3%的空間，有個卵用。
Runtian Zhou的答案很科學，雖然我也不知道那個結果怎麼推廣到帶權的問題上，但是不帶權的版本推廣起來應該是trivial的。但是我嚴重懷疑你的面試官心裡想的不是這個。
我個人感覺，這題的標準答案很可能是「多機平行計算」，因為多機圖計算這事前兩年挺熱門的。
比如這個：http://www.
graph500.org/
3樓：Runtian Zhou
USTCON是在DSPACE裡面的，複雜度是O(log2n)，改成最短路徑的話應該也差不多，參見這個鏈結
帶資源約束的最短路徑問題為什麼比帶資源約束的基本最短路徑問題容易求解？
zephyr 帶資源約束的最短路徑 shortest path problem with resource constraints 以下簡稱SPPRC 帶資源約束的基本最短路徑問題 Elementary shortest path problem with resource constraints ...
Java 崗位面試，面試官最後說，你還有什麼要問的嗎？
四猿外 我，面試了500 程式設計師的乙個技術總監，必須回答一下這個問題！首先恭喜你，如果被問到這個問題，你這輪面試基本有戲了。沒有想問的了 這種回答，差評！面試是雙向選擇，除了公司選擇你，你也要選擇公司。之前別人把你都了解透了，你還不借這個機會趕緊問問公司的情況，省的你將來入職之後再後悔。怎麼問也...
面試市場崗位，有哪些面試官會問的問題？該如何準備？
七姑娘 1.你之前做過哪些市場工作？2.對市場工作的理解 3.有什麼成功的市場案例？4.就目前的市場工作，如果有乙個case，你會如何去安排工作？ Miss 錢 1 首先先讓自己看起來有這方面相關工作經驗 1 從多看幾個成功的市場營銷的案例做起，去找一下感覺。公司除非是招實習生，其實不會真的有公司招...