Register

shortest path

• retagged by
278 views

1 Answer

0 votes
0 votes
Shortest path dont contain any "positive weight cycles". Let us see this with the help of an example

suppose the cost of A to B is 2;B to C is 5;and A to Cis:3; and this is the subgraph of a graph for which we have to calculate the shortest path. Now this cycle cant exist in the graph as we cant have all these 3 edges (u can check this by applying any shortest path algo).
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Vaishnavi01 asked Nov 19, 2018
306 views
Shortest Path
User Avatar
1 votes
1 votes
0 answers
2
Rishav Kumar Singh asked Jul 30, 2018
776 views
shortest path algo
TRUE / FALSE Explain Please.. An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1.
TRUE / FALSE Explain Please..An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have de...
User Avatar
1 votes
1 votes
3 answers
4
Abhisek Saha asked Jun 26, 2017
1,139 views
Shortest Path Algorithms
For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ? a) run dijkstra's shortest path algorithm only once. b) run dijkstra's shortest path algorithm V times. What if the given graph is directed ?
For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ?a) run dijkstra's ...
User Avatar
Link Copied!