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在循环中将所有邻居放在一起比较到源点的距离，需要额外的排序步骤，例如优先队列来优化。
对于无权图，最短路径定义为经过边数最少的路径。若不熟悉链式前向星，使用边集数组表示图也十分简便。