Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
578
questions
3
votes
3answers
1k views
Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?
Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V ...
2
votes
0answers
24 views
Shortest path in a tree
Is it correct to talk about shortest path in a tree, isn't a tree has only single path between any two nodes ?
0
votes
0answers
28 views
Algorithm to efficiently plan a path to build a pixel structure
I have a problem that I have an unsatisfactory answer to and I would be interested in knowing if there is a better solution I am missing.
The problem is as follows:
Compute a series of ...
0
votes
0answers
30 views
A relaxation-free variant of Dijkstra's shortest path algorithm
I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
0
votes
0answers
29 views
Finding the shortest distance between two nodes given multiple graphs
Assume that we have a set of nodes and multiple graphs with different edge values for the same set of nodes. As an example, there are 4 nodes A, ...
0
votes
1answer
89 views
An "easy" graph problem I can't solve
The question is:
A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2)
And a origin vertex s.
Write an efficient algorithm that finds the ...
3
votes
0answers
30 views
Shortest path which passes through a subset of vertices in an unweighted directed graph [duplicate]
Given an unweighted directed graph $G=(V, E)$, two vertices $s,t \in V$ and a subset of vertices $U \subseteq V$, suggest an algorithm which concludes if there exists a shortest path from $s$ to $t$ ...
0
votes
0answers
21 views
How to close an open polygonal chain such that the resulting enclosed area includes polygon B and excludes polygon C?
I have an algorithmic question for you:
Given: 3D triangle surface mesh, open polygonal chain A, closed polygon B, closed polygon C, all on the mesh.
Wanted: A line that closes A such that B lies ...
0
votes
0answers
29 views
How to close an open polygonal chain in clock- or counterclockwise direction?
I have an algorithmic problem that I am hoping someone can help me out with:
Given: 3D triangle surface mesh, an open polygonal chain (blue).
Wanted: A line that closes the blue line in clockwise ...
3
votes
0answers
110 views
Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work
I am looking for an algorithm to a problem that I encountered when working with 3D modeling:
On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
0
votes
0answers
14 views
Precondition of all-pairs shortest-paths algorithm
In Retiming Synchronous Circuitry , why put a negative sign to d(u) in step 1 ?
Why there is no subtraction operation for W(u, v) in step 3?
1
vote
0answers
40 views
Node disjoint paths with node splitting
I have a not so large network/graph that contains roughly 4000 edges and 1200 different nodes. Each edge has a weight (or cost) and a type (let's say either red or green). Going from one type of edge ...
-1
votes
1answer
25 views
Select the optimal edge to add to a subgraph for minimal the shortest path
The question is as follows:
Let G be connected, directed weighted Graph with non-negative edge weights and let s and t be vertices in G. Furthermore, let K be a subgraph of G with the same number of ...
0
votes
0answers
26 views
How good a center of a BFS tree is?
Consider a graph $G=(V,E)$, and a BFS tree $T$ starting from an arbitrary node $v\in V$.
Now consider finding the center node $u_T$ of $T$, i.e., the vertex with the lowest eccentricity in $T$, which ...
0
votes
0answers
12 views
SMA*+: What if a removed node gets re-generated via another predecessor?
One last question came to me while reading the paper on SMA*+ about setting the $f$-cost of nodes being re-generated.
Well, first, it looks like the part of the algorithm where we set the predecessor ...
2
votes
0answers
18 views
SMA*+: Usefulness of culling heuristics
The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost).
In the benchmark they use a culling heuristic equal ...
2
votes
0answers
17 views
SMA*+: f-cost estimation of re-generated nodes
I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my ...
2
votes
0answers
26 views
Finishing at rest at a target in 2d space
I asked a similar question here, except I forgot to specify that the final velocity must be 0.
I have 2 points in 2D space, start = $s$ and target = $t$, and a starting velocity $v_0$.
At each time ...
1
vote
1answer
18 views
Vector pathing via acceleration with velocity
I'm trying to solve a scenario where I need to find the smallest number of time steps to reach a location in 2d space, where I can manipulate the velocity with an acceleration at each time step where ...
3
votes
1answer
23 views
Shortest path in a grid with turnstile
This question is a simplification of the one about finding the shortest path in a grid with turnstile and waypoints. Since this simplification has dramatic consequences, I think it deserve its own ...
0
votes
1answer
52 views
M + N log N running time for Dijkstra
I'm taking the Design and Algorithms Part -II course in Coursera by professor Tim Roughgarden. In one of the classes, he mentioned that the running time for Dijkstra is $O(m \log n )$ using the heap ...
0
votes
1answer
75 views
Prove Edited Algorithm of Bellman–Ford?
Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.
I am stuck on this question for a week and hope to get some ...
7
votes
3answers
156 views
Shortest walk in a grid with turnstiles and waypoint
This video shows a grid maze with a type of tile that I'd call turnstiles.
The mechanics of those tiles are described below.
A turnstile tile has two bars on adjacent sides of the tile.
You cannot ...
1
vote
1answer
19 views
Algorithm for shorthest path that contains exactly n edges of weight 2 in 1,2-weighted directed graph
I am trying to find an efficient algorithm for the following problem:
Input:
weighted directed graph G=(V, E) in which all edges are weigthed either 1 or 2
s,t ∈ V
n ∈ N
Output
shortest path from s ...
0
votes
0answers
39 views
How (or why) do i find negative cycles with Johnson's algorithm
The first step of Johnson's algorithm is the creation of a new vertex s which has an edge to every other vertex with a weight of 0.
Then I perform only one iteration of the Bellman-Ford algorithm on ...
1
vote
2answers
67 views
Linear program for min-length pair of edge-disjoint paths problem
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, ...
2
votes
1answer
268 views
Shortest path given correct order of colours?
I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c_{1}, ...
1
vote
1answer
33 views
Algorithm for finding strongest connection for a user on social network
I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as:
Problem 6-1. [30 points] I Can Haz Moar Frendz?
Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a ...
0
votes
2answers
44 views
Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?
I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem.
For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with ...
1
vote
2answers
97 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, ...
1
vote
0answers
24 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, ...
1
vote
1answer
104 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, ...
0
votes
2answers
44 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:...
1
vote
0answers
24 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 ...
1
vote
1answer
42 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 ...
0
votes
1answer
95 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 ...
0
votes
1answer
50 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 ...
1
vote
1answer
50 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. ...
4
votes
1answer
66 views
Further papers or code on SMA*+?
I'm interested in the Lovinger and Zhang paper Enhanced Simplified Memory-bounded A Star (SMA*+). Are there any further papers on this algorithm or publicly-visible code (in any language) ...
1
vote
0answers
30 views
Dijkstra's algorithm - additional properties
Say we let $R$ denote the set of currently chosen vertices in Dijkstra's algorithm, $d$ be the currently stored path-length estimates, and $s$ be the source. The standard property that we know is true ...
2
votes
0answers
32 views
find zero weight cycles in a directed graph [duplicate]
I need to plan an algorithm that decides if a directed weighted graph $G = (V,E)$ has a zero weight cycle.
the graph has no negtive cycles
the algorithm needs to be in $O(|V| \cdot |E|)$ time
my ...
0
votes
0answers
43 views
Most popular path in weighted cylic directed graph
Context
I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
0
votes
0answers
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 ...
0
votes
1answer
86 views
Using A* path finding is giving me inaccurate results
So I am using A* pathfinding 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 ...
0
votes
0answers
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 ...
8
votes
0answers
349 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. ...
0
votes
0answers
63 views
What is the significance of Bellman-Ford and linear programming for scheduling and makespans?
CLRS exercise 24.4-9 says the following:
Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
0
votes
1answer
61 views
Vertices reachable from negative-weight cycles in Bellman-Ford
TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...
1
vote
1answer
78 views
Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path
Summary:
A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain ...
2
votes
1answer
59 views
shortest path in color-weighted graphs
I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum ...
