dijkstra演算法復雜度
① dijkstra演算法復雜度是多少
1、簡單復雜度是O(n2)。
Dijkstra 演算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合 Q，所以搜索 Q 中最小元素的運算（Extract-Min(Q)）只需要線性搜索 Q 中的所有元素。這樣的話演算法的運行時間是 O(n2)。
附演算法：
1functionDijkstra(G,w,s)
2foreachvertexvinV[G]
3d[v]:=infinity
4previous[v]:=undefined
5d[s]:=0
6S:=emptyset
7Q:=setofallvertices
8whileQisnotanemptyset
9u:=Extract_Min(Q)
10S:=Sunion{u}
11foreachedge(u,v)outgoingfromu
12ifd[v]>d[u]+w(u,v)
13d[v]:=d[u]+w(u,v)
14previous[v]:=u
O（n）+O（1）+O（n）+O（n^2） == O（n^2).
2、用堆優化後的時間復雜度：O((m+n)log n)
② dijkstra演算法是什麼
迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。
對於圖G=（V，E），將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為｛v0}）。第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。
堆優化
思考
該演算法復雜度為n^2,我們可以發現，如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的復雜度降為O(1)；每次調整的復雜度降為O（elogn）；e為該點的邊數，所以復雜度降為O((m+n)logn)。
實現
1、將源點加入堆，並調整堆。
2、選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。
3、處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點
1):若該點在堆里，更新距離，並調整該元素在堆中的位置。
2):若該點不在堆里，加入堆，更新堆。
4、若取到的u為終點，結束演算法；否則重復步驟2、3。
③ Floyed演算法，spfa演算法，dij演算法各自的優勢都在哪裡哪個適用於無向圖哪個適用於負權邊急！
直覺感覺是迪傑斯特拉的比較好。。。留個名。
④ 幫我解釋下網路流
必須知識：最短路徑問題
1.Dijkstra
適用於滿足所有權系數大於等於0（lij≥0）的網路最短路問題，能求出起點v1到所有其他點vj的最短距離；
樸素的Dijkstra演算法復雜度為O(N^2)，堆實現的Dijkstra復雜度為O(NlogN).
2.bellman-ford
適用於有負權系數，但無負迴路的有向或無向網路的最短路問題，能求出起點v1到所有其它點 vj的最短距離。bellman-ford演算法復雜度為O(V*E)。
3.Floyed
適用於有負權系數，可以求出圖上任意兩點之間的最短路徑。DP思想的演算法，時間復雜度為O(N^3);
for ( k= 1; k<= n; k++)
for ( i= 1; i<= n; i++)
if (graph[i][k]!=INF)
for ( j= 1; j<= n; j++)
if (graph[k][j]!=INF && graph[i][k]+graph[k][j]< graph[i][j])
graph[i][j]= graph[i][k]+ graph[k][j];
NO.1 s-t最大流
兩大類演算法
1.增廣路演算法
Ford-Fulkerson演算法: 殘留網路中尋找增加路徑
STEP0：置初始可行流。
STEP1：構造原網路的殘量網路，在殘量網路中找s－t有向路。如果沒有，演算法得到最大流結束。否則繼續下一步。
STEP2：依據殘量網路中的s－t有向路寫出對應到原網路中的s－t增廣路。對於增廣路中的前向弧，置s(e)＝u(e)- f(e)。對於反向弧，置s(e)＝f（e） STEP3：計算crement=min{s（e1），s（e2），…，s（ek）}
STEP4：對於增廣路中的前向弧，令f(e)＝f(e)＋crement；對於其中的反向弧，令f(e)＝f(e)-crement，轉STEP1。
關鍵點:尋找可增廣路。決定了演算法復雜度。
實現：Edmonds-Karp 通過採用了廣度優先的搜索策略得以使其復雜度達到O(V*E^2)。
優化—> Dinic演算法(*)
Dinic演算法的思想是為了減少增廣次數，建立一個輔助網路L，L與原網路G具有相同的節點數，但邊上的容量有所不同，在L上進行增廣，將增廣後的流值回寫到原網路上，再建立當前網路的輔助網路，如此反復，達到最大流。分層的目的是降低尋找增廣路的代價。
演算法的時間復雜度為O(V^2*E)。其中m為弧的數目，是多項式演算法。鄰接表表示圖，空間復雜度為O(V+E)。
2.預流推進演算法
一般性的push-relabel演算法: 時間復雜度達到O(V^2*E)。(*)
relabel-to-front演算法->改進
最高標號預流推進:時間復雜度O(V^2*sqrt(E))
NO2. 最小費用最大流
求解最小費用流的步驟和求最大流的步驟幾乎完全一致，只是在步驟1時選一條非飽和路時，應選代價和最小的路，即最短路。
步驟1. 選定一條總的單位費用最小的路，即要給定最小費用的初始可行流，而不是包含邊數最小的路。
步驟2. 不斷重復求最大流的步驟來進行，直到沒有飽和路存在為止。然後計算每個路的總費用。
和Edmonds-Karp標號演算法幾乎一樣，因為這兩種演算法都使用寬度優先搜索來來尋找增廣路徑，所以復雜度也相同，都是O(V*E^2)。
連續最短路演算法 + 線性規劃對偶性優化的原始對偶演算法(*)
傳說中，沒見過，據說復雜度是O(V^3)
NO3. 有上下屆的最大流和最小流（通過添加點來進行轉化）(*)
NO4. 相關圖論演算法
二分圖最大匹配： 加s和t構造最大流
專用演算法：hungary演算法 O(M*N)
二分圖最佳匹配： 加s和t構造最小費用最大流
專用演算法：KM演算法
樸素的實現方法,時間復雜度為O(n^4)
加上鬆弛函數O(n^3)
最小路徑覆蓋：
頂點數－二分圖的最大匹配
s-t最小邊割集：
最大流最小割定理：最小割等於最大流
普通最小邊割集：
Stoer-Wagner Minimum Cut O(n^3)
二分圖的最大獨立集：
N - 二分圖的最大匹配（POJ monthly）girls and boys
反證法證明
普通圖的最大獨立集是np問題。(*)
⑤ dijkstra演算法
Dijkstra演算法，一種由荷蘭科學家E.W.Dijkstra於1959年發明的尋路演算法，被譽為最短路徑求解的首選方法，優化後的復雜度可達O((m+n)log(m))。然而，其不兼容負權邊問題。
所謂負權邊，即邊的權重為負值，可以理解為在路徑中遇到這種邊後，實際成本會降低。例如，一條從A點到B點的邊，權重為-1，表示通過這條邊，從A點到B點的實際花費會減少1。
演算法的關鍵步驟是鬆弛操作，其核心原則是依據「三角形兩邊之和大於第三邊」定律，更新兩點間的最短路徑。具體操作為，對於每條邊e(v,w)，將源點s到w的距離更新為源點s到v的距離加上v到w的距離的較小值。這樣，演算法不斷調整路徑選擇，以確保找到從源點s到任一頂點w的最短路徑。
演算法執行流程可直觀理解為從起點出發，逐步擴展其可達范圍，不斷尋找距離最短的未訪問頂點。以A點作為起點，首先訪問A點，然後尋找與A相鄰未訪問的頂點B、D，計算它們到A點的距離。接著，將距離最短的頂點D加入已訪問集合S中，並從D出發繼續擴展可達范圍，尋找未訪問的鄰居頂點B、C、E，計算它們到A點的距離。在D的鄰居中，B和D到A點的距離相同，都加入結果集。然後，從B或C出發，但由於B已無未訪問鄰居，轉向C，尋找其未訪問鄰居E，並將E加入結果集中。
通過使用鏈式前向星與BFS實現該演算法，BFS在循環中將所有鄰居放在一起比較到源點的距離，需要額外的排序步驟，例如優先隊列來優化。
對於無權圖，最短路徑定義為經過邊數最少的路徑。若不熟悉鏈式前向星，使用邊集數組表示圖也十分簡便。