Graphs/Shortest Path - Revision history

Admin: /* Weighted Graphs */

2017-09-09T15:52:06Z

Weighted Graphs

← Older revision		Revision as of 15:52, 9 September 2017
Line 16:		Line 16:

	<math>		<math>
	w(P) = sum_{i=0}^{k-1} w(v_i, v_{i+1})		w(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})
	</math>		</math>

Admin: /* Unweighted Graphs */

2017-09-09T15:51:46Z

Unweighted Graphs

← Older revision		Revision as of 15:51, 9 September 2017
Line 3:		Line 3:
	==Unweighted Graphs==		==Unweighted Graphs==

	To find the shortest path from a vertex u to a vertex v on an unweighted graph, we can use a breadth-first search. A BFS results in a BFS tree; if two vertices u and v are connected by the BFS, then the BFS tree yields the shortest path by definition. This works for both directed and undirected graphs.		To find the shortest path from a vertex u to a vertex v on an unweighted graph (where "distance" is measured by number of edges), we can use a breadth-first search. A BFS results in a BFS tree; if two vertices u and v are connected by the BFS, then the BFS tree yields the shortest path by definition. This works for both directed and undirected graphs.

	See [[Graphs/BFS]].		See [[Graphs/BFS]]

			==Weighted Graphs==

			Weighted graphs assign a weight w(e) to each edge e. For an edge e connecting vertex u and v, the weight of edge e can be denoted w(e) or w(u,v).

			To find the shortest path on a weighted graph, just doing a breadth-first search isn't enough - the BFS is only a measure of the shortest path based on ''number'' of edges.

			If G is a weighted graph, the length/weight of a path is the sum of the weights of the edges that compose the path. For a path P connecting vertices v0 through vk, this is written:

			<math>
			w(P) = sum_{i=0}^{k-1} w(v_i, v_{i+1})
			</math>

			The distance d(u,v) between two vertices u and v is the length/weight of the shortest path from u to v.

			For a single source vertex s, finding the shortest path to all other nodes by using a greedy heuristic. This means iterating through each edge connected to a vertex, starting with the smallest weight (assuming you want to minimize distance).

			Dijkstra's algorithm is a weighted breadth first search. See [[Graphs/Dijkstra]].

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Notes */

2017-09-09T15:37:01Z

Notes

← Older revision		Revision as of 15:37, 9 September 2017
Line 1:		Line 1:
	=Notes=		=Notes=

	To find the shortest path from a vertex u to a vertex v, we can use a breadth-first search. A BFS results in a BFS tree; if two vertices u and v are connected by the BFS, then the BFS tree yields the shortest path by definition.		==Unweighted Graphs==

			To find the shortest path from a vertex u to a vertex v on an unweighted graph, we can use a breadth-first search. A BFS results in a BFS tree; if two vertices u and v are connected by the BFS, then the BFS tree yields the shortest path by definition. This works for both directed and undirected graphs.

	See [[Graphs/BFS]].		See [[Graphs/BFS]].

Admin: /* Notes */

2017-09-09T14:34:03Z

Notes

← Older revision		Revision as of 14:34, 9 September 2017
Line 1:		Line 1:
	=Notes=		=Notes=

	To find the shortest path from a vertex u to a vertex v, we can use a breadth-first search. See [[Graphs/BFS]].		To find the shortest path from a vertex u to a vertex v, we can use a breadth-first search. A BFS results in a BFS tree; if two vertices u and v are connected by the BFS, then the BFS tree yields the shortest path by definition.

			See [[Graphs/BFS]].

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: Created page with "=Notes= To find the shortest path from a vertex u to a vertex v, we can use a breadth-first search. See Graphs/BFS. =Flags= {{GraphsFlag}}"

2017-09-09T14:32:35Z

Created page with "=Notes= To find the shortest path from a vertex u to a vertex v, we can use a breadth-first search. See Graphs/BFS. =Flags= {{GraphsFlag}}"

New page

=Notes=

To find the shortest path from a vertex u to a vertex v, we can use a breadth-first search. See [[Graphs/BFS]].

=Flags=

{{GraphsFlag}}