1. Single-Source Shortest Paths Problem:
Input: Directed graph G=(V, E). (m=|E|, n=|V| )
-- each edge has non negative length le
-- source vertex s
Output: for each v in V, compute L(v) := length of a shortest s-v path in G
2. BFS already compute shortest paths in linear time, if le = 1 for every edge e. If we replace each edge e by directed path of le unit length edges, that will blow up graph too much.
3. Dijkstra’s Algorithm :
Initialize:
a) X = {s} [vertices processed so far]
b) A[s] = 0 [computed shortest path distances]
c) B[s] = empty path [computed shortest paths for algorithm explanation]
Main Loop:
while XǂV:
a) among all edges (v, w) in E with v in X and w not in X, pick the one that minimizes
A[v] + lvw , call it (v* , w*)
b) add w* to X
c) set A[w*] := A[v*] + lv*w*
d) set B[w*] := B[v*] U (v*, w*)
4. We cannot reduce computing shortest paths with negative edge lengths to the same problem with non negative lengths by adding large constant to edge lengths. Because paths with more edges will be added more constants which don't preserve shortest paths.
5. Correctness Proof :
Claim: For every directed graph with nonnegative edge lengths, Dijkstra’s algorithm correctly computes all shortestpath distances. Let A[v] be the shortest distance calculated by Dijkstra's algorithm and L[v] be the true shortest distance from s to v.
Proof by Induction on the number of iterations:
Base Case: A[s] = L[s] = 0.
Inductive Hypothesis: all previous iterations are correct (i.e., A[v] = L(v) and B[v] is a true shortest s-v path in G, for all v already in X).
In current iteration: Pick an edge (v*, w*) and we add w* to X. We set B[w*] = B[v*] u(v*, w*) , A[w*] = A[v*] + lv*w* = L(v*) + lv*w*. Let P= any s->w* path. It must “cross the frontier” of X and V-X.
Let y and z be the vertices on the frontier of the path, while y is in X and z isn't.
Length of P = length of s-y + lyz + length of z-w* >= L[y] + lyz >= A[v*] + lv*w*
6. Using heap to implement Dijkstra’s Algorithm:
Two Invariants :
a) elements in heap = vertices of V-X.
b) for v in heap , Key[v] = smallest Dijstra greedy score of edge (u, v) in E with u in X
By invariants, Extract-Min yields correct vertex w* to add to X and A[w*] = Key[w*].
To maintain Invariant b) :
When w* extracted from heap, for each edge (w*,v) in E:
if v in V-X :
- delete v from heap
- recompute key[v] = min{key[v] , A[w*] + lw*v }
- re-Insert v into heap
7. Running Time Analysis:
Heap operations:
- (n-1) Extract mins
- each edge (v,w) triggers at most one Delete/Insert combo (if v added to X first)
So: # of heap operations in O(n+m) = O(m) (We assume graph is connected.)
So: running time = O(m log(n))
相关推荐
Dijkstra s algorithm in matlab code. Algorithm with Computational complexity theory.
DIJKSTRA算法解释Solution to the single-source shortest path problem in graph theory
NULL 博文链接:https://shmilyaw-hotmail-com.iteye.com/blog/2010807
Dijkstra’s Algorithm 最短路径树算法,作为基本的启发式寻路方式,属于贪婪算法。在求解NPhard问题时,也仍存在其局限性
Demonstration of Dijkstra s Minimum Distance Algorithm: DIJKSTRA is a MATLAB program which runs a simple demonstration of Dijkstra s algorithm for determining the minimum distance from one node in a ...
最短路径的O(ElgV)的解法。 使用邻接表存储图,使用堆操作选取下一个最小路径点。...参考:http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
matlab开发-DijkstraAlgorithm。使用dijkstra算法计算两个节点之间的最短路径
Dijkstra’s Algorithm 地图 最短路径
本代码 利用 Dijkstra's Shortest Path Algorithm 求解有向图的最短路径。 包括 图的构建,求解过程的,排序使用的最小堆 等所有的源代码,并包括测试用例。 是学习最小堆 和 Dijkstra's Shortest Path Algorithm ...
Modify Dijkstra’s algorithm, so that it finds the hop lengths of the shortest paths from a given node s to all other nodes in a given undirected connected graph G. Note that : • find the shortest ...
Dijkstra s algorithm is an algorithm for finding the shortest paths between nodes in a graph
Dijkstra-s_Algorithm
Proof for Dijkstra´s Algorithm:Dijkstra算法证明.pdf
****实施Dijkstra算法在这个简短的项目中,我们实现了Dijkstra的算法。 我们已经获得了GUI的数据和一些代码,该GUI生成了美国城市及其之间不同连接的地图。 我们的目标是为用户计算出他们在地图上选择的任何两个...
Dijkstra s algorithm. Complexity : EllogV.
Dijkstra-s算法
这是 Dijkstra 算法的一个实现,它找到了两个节点之间的最小成本路径。 它应该解决正加权实例上的问题。
经典的dijkstra's algorithm实现,很好的例子
Dijkstra-s-Algorithm:Dijkstra算法在Python 3中的实现
基于堆实现Dijkstra算法C语言实现。。。。。。。。。。。。。。。