Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
485
questions
0
votes
0answers
22 views
Maximum weight path
While preparing for an exam, I stumbled upon a question and I'm not sure if I answered correctly. The question is:
In a directed weighted graph G in which each ...
3
votes
2answers
61 views
Shortest path between all pairs with colored nodes
I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly. The question is:
Let's say we have a directed graph with no ...
3
votes
2answers
91 views
Why doesn't Dijkstra's use a shortest-path first search?
When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we ...
0
votes
1answer
129 views
Why is my algorithm version so slow with this input?
Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (...
0
votes
0answers
36 views
Time complexity analysis of shortest path algorithm
Below is Dijkstra's algorithm from CLRS:
In the time complexity analysis of Dijkstra, CLRS says, RELAX() contains call to DECREASE-KEY(), which is essentially reducing edge weights associated with ...
0
votes
0answers
25 views
How Dijkstra's algorithm forms shortest path tree when multiple nodes have same shortest path length
I came across following problem:
Consider below graph:
What will be the shortest path tree starting with node $A$ returned by Dijkstra's algorithm, if we assume priority queue is implemented ...
1
vote
1answer
28 views
Dijkstra shortest path yields unintuitive results
Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, ...
1
vote
1answer
23 views
Dijikstra's algorithm with “hull” value catch
Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here.
Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, ...
7
votes
1answer
228 views
How hard is finding the shortest path in a graph matching a given regular language?
Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
3
votes
1answer
397 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 ...
3
votes
0answers
48 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 ...
2
votes
1answer
84 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 ...
5
votes
1answer
887 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 ...
1
vote
3answers
58 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?
0
votes
0answers
16 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 ...
3
votes
1answer
45 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 ...
1
vote
1answer
58 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 ...
2
votes
1answer
14 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'...
4
votes
1answer
45 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.
...
2
votes
1answer
25 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 ...
0
votes
0answers
92 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.
4
votes
1answer
65 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 ...
2
votes
2answers
77 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 ...
4
votes
1answer
112 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?
1
vote
1answer
139 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. ...
0
votes
0answers
24 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:
...
2
votes
0answers
17 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 [...
-2
votes
2answers
81 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
107 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 ...
1
vote
0answers
112 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.
...
0
votes
0answers
15 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 ...
2
votes
0answers
47 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 ...
2
votes
2answers
188 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 ...
0
votes
0answers
39 views
Graphs - Shortest Path Algorithms - Summary
Are following statements valid?
Shortest Path in an undirected graph can be found using BFS. Is DFS
an option here? If DFS is not an option, why.
Dijkstra's SPT works if there are no negative ...
0
votes
0answers
18 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.
...
2
votes
1answer
41 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 ...
1
vote
1answer
36 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 ...
2
votes
0answers
33 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 ...
1
vote
1answer
148 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. ...
0
votes
0answers
23 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.
2
votes
1answer
332 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 ...
1
vote
0answers
39 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 ...
0
votes
0answers
81 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 ...
2
votes
3answers
97 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 ...
0
votes
1answer
39 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?:
...
1
vote
2answers
117 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 ...
1
vote
1answer
100 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, ...
0
votes
1answer
37 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 ...
1
vote
1answer
139 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$. ...
2
votes
1answer
74 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 ...
