- With these algorithms we find shortest paths from a single source node to all other nodes.
Dijkstra's Algorithm
- If a graph contains a negative weight cycle, then some shortest paths may be found incorrectly.
- O(m.log(n)) running time using heaps. (This implementation is almost identical to prim's alg.)
- Dijkstra's algorithm is a great algorithm. If the graph fits to main memory and all edges are nonnegative and if you use heaps , you will get a very fast and always correct shortest path solutions.
- Two disadvantages: 1- Not worked for negative cycles 2- Highly centralized, not very distributed(relevant for internet routing)
Take an initial vertex S.
Relax all edges leaving the initial vertex S.
Extract minimum -> X
Relax all edges leaving X
Extract minimum -> Y
Relax all edges leaving Y
Extract minimum -> Z
Relax all edges leaving Z
Extract minimum -> Q
Relax all edges leaving Q
Extract minimum -> W
Relax all edges leaving W
Extract minimum -> E
Relax all edges leaving E
.
.
.
- Dijkstra's algorithm is an example of greedy algorithm
- Here is metu resource explaining the topic : http://cow.ceng.metu.edu.tr/Courses/index.php?course=ceng315&semester=20121
Here is an example : http://www.youtube.com/watch?v=8Ls1RqHCOPw
For unweighted graphs , we use Breadth-First Search.
Here is an image taken about DFS & BFS:
taken from : http://www.cse.unsw.edu.au/~billw/Justsearch.html
Bellman-Ford Algorithm : Finds all shortest path lengths from a source to all other nodes or determines that a negative-weight cycle exists. However, it cannot find shortest paths if there is a negative cycle ! It just detects when there is a negative cycle.
For the Bellman-Ford algorithm topic , look at here:
- Repeat the following |V|-1 times :
- relax each edge in E (relaxing is given in the question or you may take an arbitrary relaxing order)
- Test if there is any negative weight cycle by checking if d[v] > d[u] + w(u,v) for each edge (u,v).
- Advantage : Detects if a negative edge exists. However, performance of Bellman-Ford is not better than Dijkstra's algorithm.
-Used in internet routing
http://www.cs.arizona.edu/classes/cs545/fall09/ShortestPath2.prn.pdf
karabuk.edu.tr
http://ewubd.edu/~maa/Shortest%20Path%20Graphalgorithms.ppt
Notes about differences of Dijkstra's and Bellman-Ford:
1- The way we follow when we are searching a relaxing order of Dijkstra's and Bellman-Ford is different. In dijkstra we relax edges from the chosen node at each step. In Bellman-Ford relaxation may be in any order, you may choose the order , or the order may already be given with the graph.
2- In Dijkstra's, we visit each node only once. However in Bellman-Ford , we visit each node |V|-1 times since the relaxation steps loops |V|-1 times.(v:number of vertices)
Single-Source Shortest Paths in Directed Acyclic Graphs:
- An acyclic digraph is a directed graph containing no directed cycles, also known as a directed acyclic graph or a "DAG."
- There is no cycle in acyclic directed graph. Hence no negative weight cycle can exist in a DAC, and SP's are well defined.
- There can be negative edges.
- Single source shortest path problems can be solved more efficiently by using topological sort.
- By relaxing the edges of a weighted dag G=(V,E) according to a topological sort of its vertices , we can compute shortest paths from a single source in Θ (V+E) time.
Here is a some link explaining the topic and showing examples :
http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
Articulation Points is
- Any vertex whose removal results in a disconnected graph
- If v is an articulation point, then there exist distinct vertices w and x such that v is in every path from w to x
v şu durumlarda articulation point'dir:
- v depth-first tree'nin root'u ise ve en az 2 tane çocuğu varsa ,
- depth-first tree'nin non-root ve non-leaf olan v vertex'ini düşünelim. V veya v nin' subtree'lerinden birisi v'nin ancestor'larından birisine back edge yapmıyorsa,
For more information about how to find articulation point , try : http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
Biconnected Graph is:
-Any graph which does not contain articulation points.
-> Biconnected graphs have at least two vertex-disjoint paths between any pair of vertices.
->To disconnect a biconnected graph , we must remove at least two vertices.
- DFS can be used to find the biconnected components of a graph.
Here you can find a good example ,too : http://www.eecs.wsu.edu/~holder/courses/CptS223/spr08/slides/graphapps.pdf
I put the example of the above pdf :
Also , you can look at here : http://www.csie.ntu.edu.tw/~wcchen/algorithm/biconnectedGraph/algorithm.htm
Strongly Connected Component
A component C in a directed graph is strongly connected if each node u in C can reach v and v can reach u.
Examples :
1 - Give a simple example of a directed graph with negative-weight edges for which Dijkstra’s
algorithm for single source shortest paths problem produces incorrect answers.
http://www.cse.unsw.edu.au/~cs2011/05s2/assignment4-solutions.pdf
2 -2nd and 4th questions in the pdf http://www.cse.unsw.edu.au/~cs2011/05s2/Final-Practice-Problems.pdf
http://www.cse.unsw.edu.au/~cs2011/05s2/FinalPracticeSolutions.html
3 -Why is Dijkstra’s algorithm greedy?
http://thecube.ca/files/exams/2010/cs320-2010-t1-midterm1-solution.pdf
4 - 2nd and 4-c questions in https://hkn.eecs.berkeley.edu/examfiles/cs170_fa04_mt1_sol.pdf
5 - What are the advantages and disadvantages of Dijkstra's shortest path algorithm in comparison to the Bellman-Ford shortest path algorithm?
6 - 3rd question - http://www.cs.toronto.edu/~vassos/teaching/c73/old-exams/final-10.pdf
7 - Here is Stanford's video lecture and a quiz about Bellman Ford : https://class.coursera.org/algo2-2012-001/lecture
References :
strongly connected component image
strongly conected component image 2
strongly connected component image 3
.
.
- Dijkstra's algorithm is an example of greedy algorithm
- Here is metu resource explaining the topic : http://cow.ceng.metu.edu.tr/Courses/index.php?course=ceng315&semester=20121
Here is an example : http://www.youtube.com/watch?v=8Ls1RqHCOPw
For unweighted graphs , we use Breadth-First Search.
Here is an image taken about DFS & BFS:
taken from : http://www.cse.unsw.edu.au/~billw/Justsearch.html
Bellman-Ford Algorithm : Finds all shortest path lengths from a source to all other nodes or determines that a negative-weight cycle exists. However, it cannot find shortest paths if there is a negative cycle ! It just detects when there is a negative cycle.
For the Bellman-Ford algorithm topic , look at here:
- Repeat the following |V|-1 times :
- relax each edge in E (relaxing is given in the question or you may take an arbitrary relaxing order)
- Test if there is any negative weight cycle by checking if d[v] > d[u] + w(u,v) for each edge (u,v).
- Advantage : Detects if a negative edge exists. However, performance of Bellman-Ford is not better than Dijkstra's algorithm.
-Used in internet routing
http://www.cs.arizona.edu/classes/cs545/fall09/ShortestPath2.prn.pdf
karabuk.edu.tr
http://ewubd.edu/~maa/Shortest%20Path%20Graphalgorithms.ppt
Notes about differences of Dijkstra's and Bellman-Ford:
1- The way we follow when we are searching a relaxing order of Dijkstra's and Bellman-Ford is different. In dijkstra we relax edges from the chosen node at each step. In Bellman-Ford relaxation may be in any order, you may choose the order , or the order may already be given with the graph.
2- In Dijkstra's, we visit each node only once. However in Bellman-Ford , we visit each node |V|-1 times since the relaxation steps loops |V|-1 times.(v:number of vertices)
Single-Source Shortest Paths in Directed Acyclic Graphs:
- An acyclic digraph is a directed graph containing no directed cycles, also known as a directed acyclic graph or a "DAG."
- There is no cycle in acyclic directed graph. Hence no negative weight cycle can exist in a DAC, and SP's are well defined.
- There can be negative edges.
- Single source shortest path problems can be solved more efficiently by using topological sort.
- By relaxing the edges of a weighted dag G=(V,E) according to a topological sort of its vertices , we can compute shortest paths from a single source in Θ (V+E) time.
Here is a some link explaining the topic and showing examples :
http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
Articulation Points is
- Any vertex whose removal results in a disconnected graph
- If v is an articulation point, then there exist distinct vertices w and x such that v is in every path from w to x
The articulation points, bridges, and biconnected components of a connected, undirected graph. The articulation points are the heavily shaded vertices, the bridges are the heavily shaded edges, and the biconnected components are the edges in the shaded regions, with a bcc numbering shown. Resource : http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap23.htm
Theorem: In a depth-first search tree, a vertex v, other than the root, is an articulation point iff v is not a leaf and some subtree of v has no back edge to a proper ancestor of v.
How can we find articulation points?
Approach 1: Brute-force approach:
1.Delete a vertex
2.Apply DFS on the remaining vertices to see if the graph is connected,
3.Choose a new vertex and apply steps (1) and (2)
-Running time:
-O(V(V+E)) (not very efficient, it can be done in O(V+E) time!)
- v depth-first tree'nin root'u ise ve en az 2 tane çocuğu varsa ,
- depth-first tree'nin non-root ve non-leaf olan v vertex'ini düşünelim. V veya v nin' subtree'lerinden birisi v'nin ancestor'larından birisine back edge yapmıyorsa,
For more information about how to find articulation point , try : http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
Biconnected Graph is:
-Any graph which does not contain articulation points.
-> Biconnected graphs have at least two vertex-disjoint paths between any pair of vertices.
->To disconnect a biconnected graph , we must remove at least two vertices.
- DFS can be used to find the biconnected components of a graph.
Here you can find a good example ,too : http://www.eecs.wsu.edu/~holder/courses/CptS223/spr08/slides/graphapps.pdf
I put the example of the above pdf :
Also , you can look at here : http://www.csie.ntu.edu.tw/~wcchen/algorithm/biconnectedGraph/algorithm.htm
Strongly Connected Component
A component C in a directed graph is strongly connected if each node u in C can reach v and v can reach u.
Examples :
1 - Give a simple example of a directed graph with negative-weight edges for which Dijkstra’s
algorithm for single source shortest paths problem produces incorrect answers.
http://www.cse.unsw.edu.au/~cs2011/05s2/assignment4-solutions.pdf
2 -2nd and 4th questions in the pdf http://www.cse.unsw.edu.au/~cs2011/05s2/Final-Practice-Problems.pdf
http://www.cse.unsw.edu.au/~cs2011/05s2/FinalPracticeSolutions.html
3 -Why is Dijkstra’s algorithm greedy?
http://thecube.ca/files/exams/2010/cs320-2010-t1-midterm1-solution.pdf
4 - 2nd and 4-c questions in https://hkn.eecs.berkeley.edu/examfiles/cs170_fa04_mt1_sol.pdf
5 - What are the advantages and disadvantages of Dijkstra's shortest path algorithm in comparison to the Bellman-Ford shortest path algorithm?
6 - 3rd question - http://www.cs.toronto.edu/~vassos/teaching/c73/old-exams/final-10.pdf
7 - Here is Stanford's video lecture and a quiz about Bellman Ford : https://class.coursera.org/algo2-2012-001/lecture
References :
strongly connected component image
strongly conected component image 2
strongly connected component image 3
Hiç yorum yok:
Yorum Gönder