# Questions tagged [shortest-path]

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

525 questions
Filter by
Sorted by
Tagged with
448 views

### Shortest paths between given red vertices and arbitrary blue vertices

Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the ...
74 views

### Dynamic all pairs shortest path edge removal

I have a planar(|E|=O(V)) undirected graph with positive edge weights. I have already calculated all pairs shortest path with Floyd–Warshall algorithm. Now I want to recalculate APSP with an edge ...
224 views

### Dijkstra without decrease key

I was reading though this paper, which suggests using dijkstra without edge relaxation, but to rather to just insert new nodes, cf page 16 for the pseudo code. But to me the code looks wrong. I think ...
1k views

### Dijkstra with max instead of sum

Is it true that if we replace in the Dijkstra algorithm + with max, then the resulting algorithm correctly solves the problem of ...
78 views

### What's the best algorithm to find the shortest path between 2 vertices in a graph?

Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?
21 views

### Decomposition of graph to subgraphs according to parallel edges

I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges. If N parallel ...
73 views

### Maximum value of arbitrage

I'm trying to solve this from The Algorithm Design Manual: 6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time ...
124 views

### Determine shortest path in a 4x5 grid graph

Suppose we had a graph $G = (V,E)$. This graph can also be seen as a $4x5$ grid graph as shown in the image. There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and ...
16 views

### Performant algorithm to find edges without cross overs

I have a series of graphs with points plotted like this: Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don'...
78 views

### Optimal root in shortest path tree (SPT)

I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs. ...
30 views

### Proving inequalities related to Dijkstra's algorithm

Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$. Define $IN(v)$ as the set of in-neighbors of $v$. Define $w(u,v)$ as the weight of the edge $(u,v)$. I am asked to ...
251 views

### Remove a vertex from a graph keeping shortest path distance same

How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.
68 views

### Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
193 views

### How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is ...
312 views

### Modifies Dijkstra’s Algorithm to find the maximum cost path

In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?
350 views

### How does the slow All-pairs-shortest-paths algorithm work?

I am trying to fully understand the following algorithm from CLRS book: I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. ...
40 views

### How to compute the predecessor-subgraph in all-pairs-shortest-paths algorithm?

The following slow algorithm (implemented from CLRS book) which runs in $\Theta(V^4)$ works fine for computing shortest paths distances: ...
20 views

### Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees

I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [...
88 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 ...
150 views

### Algorithm to find longest path in a tree that is smaller than x

Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any ...
143 views

### C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?

I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments. The algorithm iterates over every edge in the graph. ...
18 views

### APSP on GPGPU with paths reconstruction

There is a huge number of works on efficient solution of all-pairs shortest paths (APSP) by using GPGPU. But the main goal of these works is to compute the length of the shortest path. Are there exist ...
80 views

### Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
346 views

### A* without heuristic more efficient than Dijkstra

I am using the module networkx to operate on graphs made from OpenStreetMap. I wanted to compare the shortest path algorithm to ...
21 views

### How to guarantee the minimum path removed from priority queue is the shortest path after all infinite vertices relaxed

I readed the proof of Dijkstra's algorithm in "CLRS"，and the code in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. Figure 24.7 in CLRS proofs the correctness of Dijkstra's algorithm. ...
47 views

### Thorup : What is the meaning of super distance?

While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance. It says: "For each vertex we have a super distance $D(v)\geq d(v)$" $d(v)$ must ...
37 views

### calculating a shortest path in a table structure that changes in real time

I have a table that looks like this In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user. In any moment the player ...
35 views

### Given complete graph, find optimal path with two costs on each edge

We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of ...
316 views

### Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
24 views

### Single source shortest paths with even path [duplicate]

Given directed graph with non negative weights and vertex s. I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.
591 views

### Proof that shortest path with negative cycles is NP hard

I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is ...
73 views

### Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
94 views

### Shortest path for vehicle routing problem with alternative locations

I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations. Right now, I'm trying to find ...
161 views

### Shortest path between any origin to any destination through some way stations

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm? You can visit those way stations ...
45 views

### Confused in calculating the shortest-path using Dijkstra's Algorithm [closed]

I am required to find the shortest path using Dijkstra's Algorithm. After performing the calculations, am I getting the following values correct?: ...
177 views

### Shortest path with a given condition

The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two ...
218 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, ...
44 views

### Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time

So, if I were using a black-box decision algorithm, PATH in which I could say, "does a path of weight k exist in this graph from ...
197 views

### Shortest Path in Layerwise Complete Graph

Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. ...
105 views

### Bellman-Ford - is number of interations greater than diameter?

Diameter of a connected, undirected graph is the smallest natural number d, so that between any two vertices of the graph exist path of length at most d. Prove or disprove: in Bellman-Ford is ...
54 views

### Is the number of shortest paths between every two vertices at most 4*n^3?

In every weighted graph with $n$-vertices with negative weights, with $n > 10$, a weight can't appear $n$-times in graph, there are between every two vertices at most $4n^3$ shortest paths. I'm ...
499 views

### Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|). I was thinking about using Bellman-Ford to solve the ...
226 views

### Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
60 views

### shortest path tree algorithm

Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$. I want to find an algorithm for the shortest path ...
103 views

### Path between two vertices in directed graph without cyclic vertices

I have been searching online for some time but I have not found an answer. Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic ...
2k views

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this: Breadth-...
565 views

### Djikstra's algorithm to compute shortest paths using at least k edges

I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s ...
1k views

### Multiple Source Shortest Paths in a weighted graph

In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at ...
Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$. We're looking for the shortest ...