search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Recent questions tagged shortest-path

5 votes
2 answers
1
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$
asked Sep 13, 2019 in Graph Theory gatecse 249 views
4 votes
1 answer
2
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs with negative weight edges. (S) It ... Only P, Q, S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 425 views
1 vote
1 answer
3
Consider following with respect to directed graph where there can be positive,negative edge weights but no negative edge cycle. S1 : The Bellmann Ford algorithm will compute correctly the shortest path from source vertex S to every other Vertex. S2 : The Floyd Warshall algorithm will ... every pair of Verices. Which of Following statements are Correct ? A. Only S1 B. Only S2 C. Both D. None
asked Oct 20, 2018 in Algorithms Na462 1k views
1 vote
1 answer
4
What is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ? In which line of code memoization is done? BELLMAN-FORD(G,w,s) Code 1. INITIALIZE-SINGLE-SOURCE(G,s) 2. for i = 1 to |G.V|-1 3. for each edge (u,v) ∈ G.E 4. RELAX(u,v,w) 5. for each edge (u,v) ∈ G.E ... = NIL 4. s.d = 0 RELAX(u,v,w) 1. if v.d > u.d + w(u,v) 2. v.d = u.d + w(u,v) 3. v.pi = u
asked Aug 3, 2018 in Algorithms Sandy Sharma 587 views
1 vote
0 answers
5
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.
asked Jul 31, 2018 in Algorithms Rishav Kumar Singh 232 views
0 votes
1 answer
7
In the adjacency list implementation of Bellman Ford algorithm every edge is visited at most one time and total of |E| are present in the adjacency list .So,how can the complexity be O(VE) why can't it be O(E) .Though it has two loops on whole it will run for |E| times. ??
asked Jun 1, 2018 in Algorithms kilopavan 627 views
0 votes
0 answers
9
I have a small doubt. Chapter 25 All pairs shortest path of CLRS says following: To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor matrix $\Pi=(\pi_{ij})$, where $\pi_{ij}$ ... $i$ and predecessor subgraph of $G$ for $i$) the same?
asked Mar 24, 2018 in Programming GateAspirant999 125 views
1 vote
0 answers
10
asked Dec 31, 2017 in Algorithms nikkey123 131 views
1 vote
1 answer
11
Read the following statements below For all the below questions consider the graph as simple and has positive weight edges. (i) Let the cost of the shortest path between two nodes is S.If the weight of every edge in the graph is doubled then weight of the shortest ... iii) We can use Kruskal's algorithm to find Minimum spanning tree of a directed graph . How many of the above statements are true.
asked Dec 13, 2017 in Algorithms VIKAS TIWARI 376 views
5 votes
3 answers
12
Consider the following statements with respect to a directed graph G in which edges can have positive or negative edge length but that has no negative cycles: S1 : The Bellman-Ford algorithm correctly computes shortest path lengths from a given origin s' to ... '. S2 : The Floyd-Warshall algorithm correctly computes shortest path lengths between every pair of vertices. Which of them is correct?
asked Dec 10, 2017 in Algorithms Tuhin Dutta 1.6k views
11 votes
1 answer
13
Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each vertex $\large v,$ let $\large \phi(v)$ be the length of the shortest path from $\large s$ ... $P$ is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.
asked Dec 10, 2017 in Algorithms Arjun 1.1k views
4 votes
2 answers
14
2 votes
1 answer
17
A pseudo code for Bellman Ford where each edge is relaxed k times where k>=1. Let the graph G be a simple connected and undirected graph . Let number of vertices be V, and number of edges be E . int i=1; for( i=1;i<=k;i++) { For each edge (u,v) in G { if( ... k edges. (ii) For proper running of the algorithm k can be equal to V-1. (iii) For proper running of the algorithm k must be equal to E.
asked Nov 6, 2017 in Algorithms shaurya vardhan 497 views
1 vote
0 answers
18
Hi Guys, As everyone knows Bellman Ford Algorithm works on DP approach. The algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-nmost ... converge faster. What is your opinion ? Refer --> http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/
asked Nov 3, 2017 in Algorithms Chhotu 495 views
3 votes
0 answers
19
First Statement is true. But I don't know about second?
asked Nov 2, 2017 in Algorithms Shivam Chauhan 296 views
7 votes
0 answers
20
I know that Dijkstra's Doesn't work for Negative weight cycle because it form a loop, Does it also true that it may or may not work for negative weight edge(without cycle) ? If it is not working for a negative weight edge(without cycle) give some example to prove it.
asked Oct 12, 2017 in Algorithms junaid ahmad 1.3k views
...