Recent questions tagged dijkstras-algorithm

Consider Dijkstra's algorithm on a graph having $V$ vertices and $E$ edges.Suppose an indexed priority queue is not used.Instead, the tentative distances are stored only ...

Let $G=(V,E)$ be a directed graph with positive edge weights.Given vertices $s,w,t$ we want the length of the shortest path from $s$ to $t$ that must pass through $w$.Con...

What is the primary reason to use Floyd's algorithm for the all-pairs shortest-path problem instead of Dijkstra's algorithm?Faster for dense graphs. Faster for sparse gra...

Let $G$ be a directed graph with nonnegative edge weights.Run Dijkstra's algorithm from source $s$. After the algorithm terminates, use the $\text{prev}$ pointers to cons...

Suppose every edge weight of a graph is either:a positive integer, or exactly $-1$.Consider the statement:Dijkstra's algorithm will always compute the correct shortest-pa...

Consider the following code executed while processing vertex $v$:for each edge e in G.adj(v): w = e.to() if dist[w] dist[v] + e.weight(): dist[w] = dist[v] + e.weight() ...

Let $G=(V,E)$ be a dag, where each edge is annotated with some positive length. Let $s$ be a source vertex in $G$.Suppose we run Dijkstra's algorithm to compute the dista...

Which of the following algorithms use Greedy strategy?Dijkstra's algorithmKruskal's algorithmHuffman codingBellman-Ford algorithmChoose the correct answer from the option...

What is the Time Complexity of the Dijkstra when it is using Adjacency list + Array (sorted or unsorted ) ? If it is O( V^2 + E ) then ,According to the General form of A...

Consider the below weighted graph where weight of the edge $e$ is written as $w(e).$If we run Dijkstra's algorithm with $s=0$, in which order will the vertices be deleted...

Consider the following directed, weighted graph:Even though the graph has negative weight edges, we use Dijkstra’s algorithm to calculate supposedly shortest paths from A...

Match the following:(A) Floyd Warshall(i) shortest path between two vertices(B) Dijkstra(ii) single source shortest path(C) Kruskal's(iii) Minimum spanning tree(D) Bellma...