# Questions tagged [shortest-path]

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

554 questions
Filter by
Sorted by
Tagged with
19 views

### Example of a directed graph where there are directed paths from s to every other node, but the graph does not have a shortest-path tree

I am stuck with this problem and I think a lot about the negative cycle. Can you help me with it? Thanks!
5k views

### Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete

How to show that the shortest simple path problem between two vertices $s$ and $t$ (finding a minimum weight path between $s$ and $t$) in a graph is NP-complete? I saw the following proof in a ...
114 views

### MIT 6006 Quiz 2: The shortest path task

I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course. The main idea of creating ...
324 views

### How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
630 views

### Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
67 views

### A pathfinding algorithm for graphs in which arc weights can change over time

So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction. Here's the situation, I have a weighted undirected ...
36 views

### Problem to understand a Bellman Ford algorithm exercise

I am trying to understand the following exercise from Introduction to algorithm (3rd edtion). Exercise 24.1-3 (page 654) Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, ...
41 views

### Finding the two node-disjoint paths, minimizing the sum of their lengths

Given an undirected graph and a start and end node, I am trying to find two node-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, ...
15 views

### Finding the two edge-disjoint paths, minimizing the sum of their lengths

Given an undirected graph and a start and end node, I am trying to find two edge-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, ...
20 views

### Finding shortest path for DAG using dynamic programming vs topological sort?

Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
35 views

### Shortest path algorithm where the path can travel through at most 2 vertices in X ⊂ V

I am trying to model a problem to enable me to use Dijkstra's Shortest Path algorithm. Given are a set of vertices V, and a set of vertices X ⊂ V. Between these vertices are given a set of edges where:...
18 views

### Can the Bellman-Ford Algorithm be used to find the longest path in an undirected graph through first negating the weight of all the edges? [duplicate]

I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first ...
3k views

### Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop

The Floyd-Warshall algorithm is defined as follows: ...
40 views

### Concrete example of an admissible A* heuristic compared to Djisktra

As I understand it, A* is a general form of Djikstra where the selection of the next node to visit can be based on something other than the actual distance. For example, with Djikstra, you'd use a ...
47 views

### Create Shortest Path tree for every node after Floyd Warshall in O(nm)

Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
318 views

### Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
62 views

### Using A* path finding is giving me inaccurate results

So i am using A* path finding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of ...
26 views

### How do i make sure i get the correct Bellman Ford path?

I was studying shortest path algorithms and was met with an issue regarding Bellman Ford for the image below. Following the graph, i see that node 3 has a length of 1 while node 2 has a length of 2. ...
891 views

47 views

### How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path

I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, ...
544 views

### Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
486 views

### How to extend Bellman-Ford to solve the $k$ shortest path routing?

Browsing the wikipedia I got to this page where it is said: Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
13 views

### What's the best way to combine multiple A* searches?

I have a graph that looks like this The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
33 views

### The shortest path that visits every specified node before finally reaching the specified end node?

After asking another question(Is the last step in the Christofides' algorithm necessary), I have decided Christofide's algorithm probably doesn't solve the problem I'm facing. Is there any ...
338 views

### Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph

The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics: Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
507 views

### Dijkstra without decrease key

I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new ...
33k views

### Getting negative cycle using Bellman Ford

I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name ...
34 views

51 views

### Proving that every graph has an order such that Bellman Ford can run in one iteration

I need to prove that for every given graph, that doesn't contain negative cycles, there is an order of edges so that Bellman-Ford algorithm will finish running after one iteration. I could only solve ...
111 views

### How to define a path between two sets of vertices?

In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with ...
14 views

### Genetic algorithm with a visited path list

I am currently working through the Computational Intelligence: An Introductionbook by Andries Engelbrecht. I forked a simple implementation of a genetic algorithm trying to solve a path planning ...