1樓：Drew
個人看法：在SPFA找負環的過程中，記錄乙個點進入佇列的次數。如果超過了n次，那麼這個圖就一定有環（核心條件）。
這個演算法本身複雜度還是比較優秀的。如果面對更大的資料時可以考慮用堆優化的SPFA。
2樓：Raffica
這個理由並不顯然，dfd的證明是錯的。這裡引入乙個推進的概念：
n 圖節點數 m 邊數
設每次滿足d[e.v] < d[e.u] + e.w為一次對邊e的鬆弛，
設最後一次在佇列中訪問某個點i的時間戳為t[i]，
求最短路過程可以看成在佇列中的節點在最短路樹上的『推進』過程，這裡給出以不同形式描述的推進的定義：
1、乙個節點被推進，當且僅當這個節點對應的路徑已經在最短路樹上，（也就是說後面可能被鬆弛的那種不算在內，每次推進不可能使得已經被推進過的節點再被更新）
2、假設我們已知這棵最短路樹，那麼我們SPFA的過程就是在原圖上BFS，當且僅當某個節點以及它的所有祖先全部在這棵最短路樹上時，它被推進，設乙個節點i被推進後的所有節點中最晚的那個時間戳為t[j]，則很容易發現t[j] - t[i] < m(雖然這個結論P用沒有)；
3、最後一次訪問某個節點並鬆弛對應的邊的過程稱為推進
Lemma.1 最短路樹的高度不可能大於n：顯然。
Lemma.2 假設每個節點i被訪問過f[i]次，f[i]不可能大於節點i在最短路樹的高度h[i]：通俗的理解就是推進h[i]次後這個節點就不可能被訪問了；嚴謹地，對此處語境中的推進進行定義：
一次推進指在最短路樹上某個深度上的點全部通過SPFA的過程確定了距離的過程。
根據2個Lemma，乙個節點i在被訪問超過h[i]（這時候還有最短路樹嗎？）次後肯定能確認是否有負環。h[i] < n，QED
如何理解最優化搜尋中的Wolfe準則？
Wolfe conditions i ii with 講講Wolfe準則是怎麼設計出來的，就很容易理解了。Wolfe 準則主要用於線搜尋line search，由兩個條件組成，i Armijo condition和ii curvature condition。Armijo condition是充分下...
電腦太卡，如何最好優化，最好的電腦優化和清理軟體是什麼？
最好的清理軟體 自帶的磁碟清理 不放心選CCleaner最好的優化軟體 感覺是DISM 再說全體。解除安裝掉所有安全軟體，使用Windows Defender。少用國內流氓 一切管家 多用一些好軟體 去知乎的軟體話題去找 要是還卡，至少換塊固態盤。 小奧 更新一下 那個優化程序優先順序的軟體在如今沒...
如何優化 Python 爬蟲的速度？
我之前弄過分布式爬蟲，爬取速度和你的機器數量成正比。整體架構如下 scrapy 從訊息佇列rabbitmq裡獲取起始url，然後處理後的訊息儲存到mongodb裡。然後通過docker批量部署映象到不同的機器。scrapy有致命缺點，就是源站響應很慢的化，大部分cpu會閒置，這樣你即使把併發設定的很...