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.

Filter by
Sorted by
Tagged with
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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'...
-1
votes
1answer
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 ...
-1
votes
3answers
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?
-2
votes
2answers
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 ...
-2
votes
2answers
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 ...
-2
votes
1answer
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 ...
-2
votes
1answer
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?
-2
votes
1answer
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. ...
-2
votes
1answer
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)...
-2
votes
1answer
97 views

Shortest path with no two consecutive edges from a certain edge set

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 ...
-3
votes
1answer
1k views

Best heuristic for A*? [closed]

I'm trying to build a maze solver using A* algorithm. The maze is a grid with movement allowed in 4 directions (up, down, left, right). If there's a starting cell (x1, y1) and a destination (x2, y2), ...