假設頂點是\(V_0到V_5\) 六個點，開始時候是沒有連線的，但是已知能互相到達的頂點之間的邊權。
步驟是每次從頂點0開始查找，找出距離頂點最短的點，然後标記該點為true,再查詢該點能直達的其他點加上邊權會不會比原先記錄的距離值小--->即更新最短距離；周遊完了所有從該點能到的點後再次回到起點。
樹與圖的存儲
樹是一種特殊的圖，與圖的存儲方式相同。
對于無向圖中的邊ab，存儲兩條有向邊a->b, b->a。
是以我們可以隻考慮有向圖的存儲。
(1) 鄰接矩陣：<code>g[a][b]</code> 存儲邊<code>a->b</code>
(2) 鄰接表：
// 對于每個點k，開一個單連結清單，存儲k所有可以走到的點。h[k]存儲這個單連結清單的頭結點
當這個圖是n個點 m條邊的無向圖時，那麼<code>m可能和 n的2倍差不多</code>:
這時， 不妨設<code>M = 2 * N</code>
<code>h[N]</code> <code>e[M]、ne[M]</code>
時間複雜度<code>O(n+m)</code>,n表示點數，m表示邊數
(1)深度優先周遊
(2)橫向優先搜尋
樸素版dijkstra算法适合稠密圖，用鄰接矩陣存儲
堆優化版适合稀疏圖，用鄰接表存儲 點的範圍較大--稀疏圖
時間複雜是 \(O(n^2+m)\), n 表示點數，m 表示邊數
1、當到一個時間點時，圖上部分的點的最短距離已确定，部分點的最短距離未确定。
2、選一個所有未确定點中離源點最近的點，把他認為成最短距離。
3、再把這個點所有出邊周遊一邊，更新所有的點。
算法設計：貪心
st[]更确切的含義是某個點是否已經更新過其他點，st最短路确定而不是它的最短距離是否已經确定。是以更新其他點的距離時，前面更新過的點也要更新 其實也可以加上<code>if(!st[j])</code>
思路：
集合S中的點表示已經找到最短路徑
一些問題：
在更新dist時，有可能兩個點重複進堆，有的點它既是a的鄰接點又是b的鄰接點，這樣的點可能會在更新a的鄰接點時加進一次，右在更新b的鄰接點的時再進入一次，這樣隊列中就有兩個一樣的點，雖然距離不同，是以用<code>st</code> 數組對已經找出最短路徑的點進行标記，避免重複計算
題目：有邊數限制的最短路a
單源最短路徑算法
對于帶權有向圖 G = (V, E)，Dijkstra 算法要求圖 G 中邊的權值均為非負，而 Bellman-Ford 算法能适應一般的情況（即存在負權邊的情況）。一個實作的很好的 Dijkstra 算法比 Bellman-Ford 算法的運作時間要低。
設計：動态規劃
時間複雜度：\(O(V*E)\) 頂點數 邊數, \(n頂點數，m邊數\)
了解：對所有邊進行\(n-1\)次松弛操作,因為在一個含有n個頂點的圖中，任意兩點之間的最短路徑最多包含n-1條邊，
換句話說，第1輪在所有邊進行松弛後，得到的是源點最多經過1條邊到達其他頂點的最短距離；
第2輪在對所有的邊進行松弛後，得到的是源點最多經過2條邊到達其他頂點的最短距離；
算法描述：
1、\(dist[N]\)數組表示源頂點到所有頂點的距離，初始化為\(infinte\),\(dist[1][1]=0\),
2、計算最短路徑，執行\(V-1\)次周遊
對于圖中的每條邊：如果起點到u的距離d加上權值w小于到終點v的距離，更新終點v的距離值d
\(if(dist[b]>dist[a]+w) dist[b]=dist[a]+w\)
例如以下加上一個拷貝數組就可以求最多經過k條邊的最短距離
判斷是否有負權環，再對邊進行一次額外的周遊，如果還能更新說明仍然存在一條邊使得兩點距離更短，事實上再更新多次還是有更新的情況。
注意：
如果不限制邊數，直接求最短路，不需要拷貝數組
如果限制邊數，則需要拷貝數組
為什麼是<code>> 0x3f3f3f3f / 2</code> (主要還是因為每條邊都周遊了，周遊了很多無用的邊)
題目： spafa判斷負環
spfa求最短路
https://blog.csdn.net/qq_35644234/article/details/61614581 這篇部落格給出了過程
https://www.cnblogs.com/acioi/p/11694294.html spfa求負環的解釋
時間複雜度 平均情況下 \(O(m)\)，最壞情況下 \(O(nm)\), n 表示點數，m 表示邊數
\(SPFA算法\)是對上面的\(bellmanford\)算法的隊列優化
算法描述：首先建立一個隊列，初始隊列裡隻有起始點，建立一個表格記錄起始點到所有點的最短路徑(初始值賦為極大值)，然後進行松弛操作，依次用隊列中的點去重新整理起始點到所有點的最短路，如果重新整理成功且被重新整理點不在隊列中則把其加入到隊列中。
求負環：如果某個點進入隊列的次數超過N次則存在負環(N為圖的頂點數)
最優解法：用一個cnt[i] 數組記錄目前到 到 i 點的最短路徑上經過的點的數量，如果 出現<code>cnt[i] > n</code>說明出現了負環。也可統計邊數，當<code>邊數 >= n</code>時也是出現了負環。
<code>st</code>數組的作用隻是記錄目前有哪些點在隊列中
\(Floyd\)算法屬于暴力求解，時間複雜度\(O(n^3)\),\(n\)表示點數
判斷無最短路徑的方法是<code>> inf / 2</code>, 原因：加入求1~6個點的距離，6是終點，
<code>d[1][5] = 0x3f</code>，1到5不可達，此時 <code>d[5][6] = -4</code>, <code>d[1][6] = d[1][5] + d[5][6] !=0x3f</code>但是大于0x3f/2。此時1到6是不可達的。
題目：有向無環圖的拓撲序列
在圖論中，拓撲排序是一個有向無環圖的所有頂點的線性序列：
1、每個頂點出現一次
2、若存在一條從A到B的路徑，那麼在序列中頂點A在B的前面。
一個有向無環圖一定至少存在一個入度為0的點
如何求拓撲序列？
拓撲序列中，所有的邊都是從前往後的，是以入度為0的點都可以作為起點，将所有入度為0的點入隊，因為前面沒有點指向它，它隻能指向後面的點
入隊之後，将它指向的終點的入度減去1
入度為0的點入隊
周遊t的所有出邊
完整模闆
![線程同步，可重入鎖，synchronized[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)