Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
463
questions
1
vote
1answer
21 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
37 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
35 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
15 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
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
67 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
34 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
13 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
42 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
79 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
36 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
38 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
32 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
72 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
21 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
146 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
22 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
70 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
69 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
35 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
82 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
62 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
33 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
105 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
50 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 ...
1
vote
1answer
46 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 ...
2
votes
0answers
93 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 ...
3
votes
2answers
125 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 ...
2
votes
1answer
51 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 ...
4
votes
1answer
100 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 ...
11
votes
3answers
1k views
What is the meaning of 'breadth' in breadth first search?
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-...
0
votes
0answers
34 views
Implementation of multiple sink shortest pair of disjoint paths problem for multigraphs
I would like to implement the shortest pairs of edge-disjoint paths of Suurballe and Tarjan for multigraphs in the interpretation of Banerjee et al. (http://web.cs.iastate.edu/~pavan/papers/short.pdf, ...
1
vote
1answer
222 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 ...
3
votes
1answer
341 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 ...
0
votes
1answer
51 views
Minimal paths as solution of a linear program of a special network flow
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 ...
0
votes
0answers
182 views
How can an A* algorithm visit all nodes?
Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
2
votes
1answer
170 views
Given directed connected weighted graph, check if d(v) = delta(s,v)
I'm having some hard time with this problem.
Can someone give me some clue/guidance?
This is an homework question, so please don't just solve it.
Given a weighted directed connected graph $G = (V,...
1
vote
1answer
266 views
Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis
Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
4
votes
0answers
84 views
Can the running time be reduced to something lower than $O(d^4)$?
Imagine I have a weighted complete directed graph $G$ with $d$ vertices(so $d(d-1)$ edges) and I want to do the following:
Set $D$ to be a DAG with the same set of vertices but without any edges
sort ...
0
votes
1answer
17 views
Term for an A*-like pathfinding strategy where only the heuristic goal distance matters
I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...
0
votes
1answer
77 views
Hitting probability of random walk within given number of steps
Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates.
What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially?
We can ...
1
vote
1answer
236 views
Floyd–Warshall algorithm on an undirected graph contains negative weight edges
According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances ...
6
votes
1answer
148 views
Finding a negative cycle in a bipartite graph
The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where ...
0
votes
1answer
61 views
Distance function such that we visit every “color region” once [closed]
Consider the following image:
Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right.
We must go through each color exactly once, and once we go outside a color, ...
3
votes
1answer
126 views
Constructing a minimum spanning tree from an all-shortest path graph?
Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a ...
1
vote
1answer
61 views
Combinatorial Optimization: Shortest distance given sets of drivers and riders
Problem:
I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to ...
2
votes
2answers
225 views
Given all pairs shortest paths matrix, find graph with minimum total sum of edges
I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some ...
