The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [shortest-path]

Questions about the algorithmic problems of finding shortest paths between nodes in a graph.

463 questions
Filter by
Sorted by
Tagged with
96 views

Computer Networks, OSI model

What layer of OSI model does define the route of information transmission between sender and receiver computers? A) Session layer B) Physical layer C) Data link layer D) Network layer E) Transport ...
413 views

Finding multiple shortest path trees from an undirected, weight graph

In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree. How do I find an ...
24 views

What algorithm to apply when a graph have cycles (“circuits”) and some negatives values in order to find the shortest path from $x1$ to all vertices?

What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices? For instance in the following graph? I know I can'...
104 views

Minimising two maximum edges in s-t path

I've been trying to solve the following problem: Problem is the following: Given a graph and a pair of nodes $s$, $t$ you have to find the path from $s$ to $t$ which minimises the sum of its two ...
304 views

BFS in K shortest paths

Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes? If so where can it be useful?
476 views

When is bidirectional search unusable?

Is there any situation that bidirectional search on a graph is not applicable? for example is there any classes of graph that we can only use ordinary Dijkstra's algorithm, and can not use its ...
73 views

Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?

I claim to have solved the travelling salesman problem as follows. (You will have to be familiar with djikstra's algorithm for this.) 1) I am about to start using djikstra's algorithm on any given ...
546 views

Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ...
382 views

Find the weight of the lightest path from u to v

Find the weight of the lightest path from u to v the goes through node a or/and b. Do you have a suggestion on how it can be done?
125 views

why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm

We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists. ...
572 views

Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification

I provided my answers in the "answer your own question" bit. I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though? a)...
Given a graph with nodes $N$ and two sets of edges $E_1$, $E_2$ where no two edges from $E_2$ can be used consecutively, find the shortest path between $n_1, n_2 \in N$. Is there a smart way to ...