Graphs/Dijkstra - Revision history

Admin: /* Reconstructing Shortest Path Tree */

2017-09-10T18:42:36Z

Reconstructing Shortest Path Tree

← Older revision		Revision as of 18:42, 10 September 2017
Line 121:		Line 121:
	==Reconstructing Shortest Path Tree==		==Reconstructing Shortest Path Tree==

	The above pseudocode yields a distance map - each entry/key is a vertex that maps to a value that is the shortest distance from the source node to the given vertex.		The above pseudocode yields a distance map - each entry/key is a vertex that maps to a value that is the shortest distance from the source node to the given vertex. This is useful, but not as useful as a tree structure that would not just give the distance but actually give THE PATH.

			We can construct the shortest path tree from the distance map using the edge relaxation relation: namely, that if u is the vertex that precedes the last vertex v on the shortest path, the following must be true:

			<pre>
			distance[u] + w(u,v) = distance[v]
			</pre>

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Notes */

2017-09-10T18:40:28Z

Notes

← Older revision		Revision as of 18:40, 10 September 2017
Line 1:		Line 1:
	=~~Notes~~=		=Goodrich Chapter 12=

	Dijkstra's algorithm is a weighted breadth-first search. it uses a greedy heuristic to select the next edge. It works by starting with an empty "cloud" of vertices, and adds vertices to the cloud in order of their distance from s.		Dijkstra's algorithm is a weighted breadth-first search. it uses a greedy heuristic to select the next edge. It works by starting with an empty "cloud" of vertices, and adds vertices to the cloud in order of their distance from s.
Line 118:		Line 118:

	If we want to achieve further improvements, we can use a Fibonacci heap, which is a more advanced data structure allowing for a big O cost of <math>O(m + n \log n)</math> runtime.		If we want to achieve further improvements, we can use a Fibonacci heap, which is a more advanced data structure allowing for a big O cost of <math>O(m + n \log n)</math> runtime.

			==Reconstructing Shortest Path Tree==

			The above pseudocode yields a distance map - each entry/key is a vertex that maps to a value that is the shortest distance from the source node to the given vertex.

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Implementations */

2017-09-10T18:38:56Z

Implementations

← Older revision		Revision as of 18:38, 10 September 2017
Line 101:		Line 101:
	If we use an unsorted priority queue, we require more time to extract the minimum but less time to update items - removing minimum costs <math>O(n)</math> but updating requires <math>O(1)</math>. Thus, the implementation is <math>O(n^2 + m)</math>, or just in terms of n, <math>O(n^2)</math>.		If we use an unsorted priority queue, we require more time to extract the minimum but less time to update items - removing minimum costs <math>O(n)</math> but updating requires <math>O(1)</math>. Thus, the implementation is <math>O(n^2 + m)</math>, or just in terms of n, <math>O(n^2)</math>.

	==~~Implementations~~==		===Implementation Choices===

	From the above we can see we have two choices for implementing the priority queue:		From the above we can see we have two choices for implementing the priority queue:

Admin: /* Big O Cost */

2017-09-10T12:24:33Z

Big O Cost

← Older revision		Revision as of 12:24, 10 September 2017
Line 80:		Line 80:

	<math>		<math>
	\sum_{v \in G} \mbox{~~outdeg~~}(u)		\sum_{v \in G} \mbox{outdegree}(u)
	</math>		</math>

Line 97:		Line 97:
	* m calls to update method of pq		* m calls to update method of pq

	Each of the above operations can be run in <math>O(log n)</math> if we implement the priority queue as a heap, giving an overall big O cost of <math>O((n+m) \log n)</math>, or, writing only in terms of n, <math>O(n^2 \log n)</math>.		Each of the above operations can be run in <math>O(\log n)</math> if we implement the priority queue as a heap, giving an overall big O cost of <math>O((n+m) \log n)</math>, or, writing only in terms of n, <math>O(n^2 \log n)</math>.

	If we use an unsorted priority queue, we require more time to extract the minimum but less time to update items - removing minimum costs <math>O(n)</math> but updating requires <math>O(1)</math>. Thus, the implementation is <math>O(n^2 + m)</math>, or just in terms of n, <math>O(n^2)</math>.		If we use an unsorted priority queue, we require more time to extract the minimum but less time to update items - removing minimum costs <math>O(n)</math> but updating requires <math>O(1)</math>. Thus, the implementation is <math>O(n^2 + m)</math>, or just in terms of n, <math>O(n^2)</math>.

Admin: /* The Central Idea: Edge Relaxation */

2017-09-10T12:22:08Z

The Central Idea: Edge Relaxation

← Older revision		Revision as of 12:22, 10 September 2017
Line 5:		Line 5:
	The end result of Dijkstra's algorithm is the length of the shortest distance (weighted path) from the source vertex s to all other vertices v on the graph G.		The end result of Dijkstra's algorithm is the length of the shortest distance (weighted path) from the source vertex s to all other vertices v on the graph G.

	==~~The Central Idea:~~ Edge Relaxation==		==Edge Relaxation==

	The central idea in Dijkstra's algorithm is edge relaxation. To implement edge relaxation, we define a starting vertex s, and a map distance, which maps vertices to distances.		The central idea in Dijkstra's algorithm is edge relaxation. To implement edge relaxation, we define a starting vertex s, and a map distance, which maps vertices to distances.

Admin: /* Implementations */

2017-09-10T12:20:49Z

Implementations

← Older revision		Revision as of 12:20, 10 September 2017
Line 115:		Line 115:
	Therefore, for a small number of edges, <math>m < \dfrac{n^2}{\log n}</math> we go with the heap-based implementation. For a larger number of edges <math>m > \dfrac{n^2}{\log n}</math>, we go with an unsorted sequence implementation.		Therefore, for a small number of edges, <math>m < \dfrac{n^2}{\log n}</math> we go with the heap-based implementation. For a larger number of edges <math>m > \dfrac{n^2}{\log n}</math>, we go with an unsorted sequence implementation.

	Dijkstra's algorithm can therefore compute the distance from s to all other vertices on the graph G in the better of <math>O(n^2)</math> and <math>O(n+m)\log n)L</math> time.		Dijkstra's algorithm can therefore compute the distance from s to all other vertices on the graph G in the better of <math>O(n^2)</math> and <math>O((n+m)\log n)</math> time.

	If we want to achieve further improvements, we can use a Fibonacci heap, which is a more advanced data structure allowing for a big O cost of <math>O(m + n \log n)</math> runtime.		If we want to achieve further improvements, we can use a Fibonacci heap, which is a more advanced data structure allowing for a big O cost of <math>O(m + n \log n)</math> runtime.

Admin: /* Implementations */

2017-09-10T09:30:44Z

Implementations

← Older revision		Revision as of 09:30, 10 September 2017
Line 113:		Line 113:
	Both implementations are about equal in complexity of the algorithm, and both are about equal in constant factors for worst-case running time.		Both implementations are about equal in complexity of the algorithm, and both are about equal in constant factors for worst-case running time.

	Therefore, for a small number of edges, <math>m < \dfrac{n^2}{\log n}</math> we go with the heap-based implementation. For a larger number of edges <math>m > \dfrac{n^2}{\log n}<m/~~ath~~>, we go with an unsorted sequence implementation.		Therefore, for a small number of edges, <math>m < \dfrac{n^2}{\log n}</math> we go with the heap-based implementation. For a larger number of edges <math>m > \dfrac{n^2}{\log n}</math>, we go with an unsorted sequence implementation.

	Dijkstra's algorithm can therefore compute the distance from s to all other vertices on the graph G in the better of <math>O(n^2)</math> and <math>O(n+m)\log n)L</math> time.		Dijkstra's algorithm can therefore compute the distance from s to all other vertices on the graph G in the better of <math>O(n^2)</math> and <math>O(n+m)\log n)L</math> time.

Admin: /* Implementations */

2017-09-10T09:30:22Z

Implementations

← Older revision		Revision as of 09:30, 10 September 2017
Line 109:		Line 109:
	The heap implementation requires <math>O((n+m) \log n)</math>		The heap implementation requires <math>O((n+m) \log n)</math>

	The unsorted sequence implementation requires <math>O(n^2)</.math>		The unsorted sequence implementation requires <math>O(n^2)</math>

	Both implementations are about equal in complexity of the algorithm, and both are about equal in constant factors for worst-case running time.		Both implementations are about equal in complexity of the algorithm, and both are about equal in constant factors for worst-case running time.

Admin: /* Dijkstras Agorithm Psuedocode */

2017-09-10T09:30:06Z

Dijkstras Agorithm Psuedocode

@@ Line 64: / Line 64: @@
      return distance
 </pre>
 =Flags=
 {{GraphsFlag}}

Admin: /* Dijkstras Agorithm Psuedocode */

2017-09-10T08:35:40Z

Dijkstras Agorithm Psuedocode

← Older revision		Revision as of 08:35, 10 September 2017
Line 62:		Line 62:
	distance[v] = distance[u] + w(u,v)		distance[v] = distance[u] + w(u,v)
	update pq[v] with new value of distance[v]		update pq[v] with new value of distance[v]
			return distance
	</pre>		</pre>