# Recent questions tagged shortest-path

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$
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
1 vote
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
1 vote
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
1 vote
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.
1 vote
6
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????
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. ??
8
Is it Dynamic programming?
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?
1 vote
10
1 vote
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.
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?
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.
14
–1 vote
15
16
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.
1 vote