做外贸的在哪些网站找工作,如何找网站制作,软件开发平台的选择,想建网站须要什么条件算法介绍
源点s,数组d[u]表示s到u的最短距离#xff0c;空集S#xff0c;点集Q初始化#xff1a;将源点s从点集中去掉#xff0c;加入S#xff0c;d[s]0#xff0c;∀v∈Q,d[v]w[s][v]\forall v\in Q ,d[v]w[s][v]∀v∈Q,d[v]w[s][v]将Q中d[v]最小的点去掉加入S,并对u∈…算法介绍
源点s,数组d[u]表示s到u的最短距离空集S点集Q初始化将源点s从点集中去掉加入Sd[s]0∀v∈Q,d[v]w[s][v]\forall v\in Q ,d[v]w[s][v]∀v∈Q,d[v]w[s][v]将Q中d[v]最小的点去掉加入S,并对u∈Q,w[v][u]∞u\in Q,w[v][u]\inftyu∈Q,w[v][u]∞进行松弛操作如果d[v]w[v,u]d[u],d[u]d[v]w[v,u]d[v]w[v,u]d[u],d[u]d[v]w[v,u]d[v]w[v,u]d[u],d[u]d[v]w[v,u]重复上述步骤直到Q为空集
正确性证明
Dijkstra算法条件没有负边
设源点为sd[v]表示源点到点v的举例d[u,v]表示点u到点v的举例w[u,v]表示从点u到点v的一条有向边的长度δ(s,v)\delta(s,v)δ(s,v)表示源点到点v的最短路径长度。
最优子结构性质任意两点之间的最短路径的子路径仍然是最短路径
证明假设s到v的最短路径上有子路径u到w那么δ(s,v)d[s,u]d[u,w]d[w,v]\delta(s,v)d[s,u]d[u,w]d[w,v]δ(s,v)d[s,u]d[u,w]d[w,v]d[u,w]δ(u,w)d[u,w]\delta(u,w)d[u,w]δ(u,w)
那么将d[u,w]d[u,w]d[u,w]替换为δ(u,w)\delta(u,w)δ(u,w)可以得到更好的路径那么原路径就不知最短路径这和δ(s,v)\delta(s,v)δ(s,v)的定义矛盾。因此该问题具有最优子结构性质。
引理1初始化以后进行松弛操作前后∀v∈V,d[v]⩾δ(s,v)\forall v \in V, d[v]\geqslant \delta(s,v)∀v∈V,d[v]⩾δ(s,v)
证明由初始化条件刚初始化以后∀v∈V,d[v]⩾δ(s,v)\forall v \in V, d[v]\geqslant \delta(s,v)∀v∈V,d[v]⩾δ(s,v)
假设当对点v进行松弛操作时第一次导致上式不再成立即d[v]d[u]w[u,v]δ(s,v)d[v]d[u]w[u,v]\delta(s,v)d[v]d[u]w[u,v]δ(s,v)
因为点u在点v之前所以点u满足上述不等式d[u]⩾δ(s,u)d[u]\geqslant \delta(s,u)d[u]⩾δ(s,u)
由定义容易得到w[u,v]⩾δ(u,v)w[u,v]\geqslant \delta(u,v)w[u,v]⩾δ(u,v)因此d[v]d[u]w[u,v]⩾δ(s,u)δ(u,v)d[v]d[u]w[u,v]\geqslant \delta(s,u)\delta(u,v)d[v]d[u]w[u,v]⩾δ(s,u)δ(u,v)
由三角不等式d[v⩾δ(s,u)δ(u,v)⩾δ(s,v)d[v\geqslant \delta(s,u)\delta(u,v)\geqslant \delta(s,v)d[v⩾δ(s,u)δ(u,v)⩾δ(s,v)与上面假设矛盾
因此初始化以后进行松弛操作前后∀v∈V,d[v]⩾δ(s,v)\forall v \in V, d[v]\geqslant \delta(s,v)∀v∈V,d[v]⩾δ(s,v)引理1成立
引理2假设存在s到v的最短路径:s-…-u-vd[u]δ(s,u)d[u]\delta(s,u)d[u]δ(s,u)那么在点u对v进行松弛操作d[v]d[u]w[u,v]d[v]d[u]w[u,v]d[v]d[u]w[u,v]之后d[v]δ(s,v)d[v]\delta(s,v)d[v]δ(s,v)
证明由最优子结构性质s到v的路径中s到u为点u的最短路径δ(s,v)δ(s,u)w[u,v]\delta(s,v)\delta(s,u)w[u,v]δ(s,v)δ(s,u)w[u,v]
d[u]w[u,v]δ(s,u)w[u,v]δ(s,v)d[u]w[u,v]\delta(s,u)w[u,v]\delta(s,v)d[u]w[u,v]δ(s,u)w[u,v]δ(s,v)由引理1在松弛操作以前d[v]⩾δ(s,v)d[v]\geqslant \delta(s,v)d[v]⩾δ(s,v)因此松弛操作会保证d[v]δ(s,v)d[v]\delta(s,v)d[v]δ(s,v)等证。
当算法结束后d[v]δ(s,v)d[v]\delta(s,v)d[v]δ(s,v)
证明因为算法中将点加入确定的集合后就不再进行修改所以相当于证明加入确定集合时d[v]δ(s,v)d[v]\delta(s,v)d[v]δ(s,v)
由引理1假设加入确定集合时第一个出现d[v]δ(s,v)d[v]\delta(s,v)d[v]δ(s,v)为节点v(开始使用反证法)
假设s到v的最短路径为s-…-x-y-…-vx是该路径在确定集合中的最后一个元素y是该路径不在确定集合中的第一个元素。
因为v是第一个出现的点而x在v之前加入所以d[x]δ(s,x)d[x]\delta(s,x)d[x]δ(s,x)
由最优子结构s-…-x-y是s到y的一条最短路径此时x已经进行了松弛操作
由引理2d[y]δ(s,y)d[y]\delta(s,y)d[y]δ(s,y)
因为y是s到v路径上的一点所以δ(s,v)⩾δ(s,y)\delta(s,v)\geqslant \delta(s,y)δ(s,v)⩾δ(s,y)
加入确定集合时d[v]d[v]d[v]是所有未加入点中最小的所以d[v]⩽d[y]δ(s,y)⩽δ(s,v)d[v]\leqslant d[y]\delta(s,y)\leqslant\delta(s,v)d[v]⩽d[y]δ(s,y)⩽δ(s,v),与假设矛盾。证毕。
复杂度分析
初始化的复杂度为Θ(∣V∣)\Theta(|V|)Θ(∣V∣)
总共要循环|V|次寻找点集中d[]最小的元素复杂度为O(∣V∣T寻找最小元素)O(|V|T_{寻找最小元素})O(∣V∣T寻找最小元素)
对于每个点都需要对所指向的点进行降低键值操作由握手定理总共需要降低出度的总和即|E|复杂度为O(∣E∣T降低键值)O(|E|T_{降低键值})O(∣E∣T降低键值)
因此总共的复杂度为O(∣V∣T寻找最小元素∣E∣T降低键值)O(|V|T_{寻找最小元素}|E|T_{降低键值})O(∣V∣T寻找最小元素∣E∣T降低键值)通过使用不同的数据结构我们可以得到不同的复杂度。特殊的如果我们使用数组复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)如果我们使用二叉堆复杂度为O((VE)logV)O((VE)logV)O((VE)logV)如果我们使用斐波那契堆可以得到最优秀的复杂度O(EVlogV)O(EVlogV)O(EVlogV)
和BFS的关系
特殊地如果边的权值全部为1或者相等那么BFS就是Dijkstra算法复杂度为O(VE)O(VE)O(VE)
