Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
550
questions
2
votes
0answers
27 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
38 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) = ...
-1
votes
0answers
47 views
Find an minimum weight elementary path with a given constraint
I have a problem as below and I am really stuck with it as it run with more than the time I desired (about 1 second). I really want your help to build up a more efficient algorithms than mine
Given ...
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
47 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 ...
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 ...
10
votes
0answers
323 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
18 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
14 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
51 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
28 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 ...
1
vote
2answers
97 views
Minimum distance in an undirected weighted graph to cover k nodes using teleportations
I have been practicing problems on graphs and shortest paths and
I encountered a problem that I'm struggling to understand.
Can you give me any tips and/or can you confirm that I got the general
...
1
vote
1answer
44 views
Can the loops be in any order in the Floyd-Warshall algorithm?
I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:
...
0
votes
0answers
15 views
Min-plus matrix and Shortest path variation
I was solving a problem in which given a directed weighted graph with no self loops (adjacency matrix),I had to find minimum path of length at least K between ever pair of nodes.
One method is :
let ...
0
votes
1answer
35 views
Shortest Path with a twist
We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can ...
2
votes
1answer
153 views
Bellman Ford facts and specific question
The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following:
$d(v)>d(u)+w(u,v)$
holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)...
1
vote
0answers
44 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 ...
2
votes
1answer
108 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 ...
0
votes
0answers
11 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 ...
1
vote
0answers
20 views
Solving multiple pathfinding problems efficiently
Let $V$ be a set of nodes, $c : V \times V \rightarrow \mathbb{R} \cup \{\infty\}$ be an edge cost function, and $h : V \times V \rightarrow \mathbb{R}$ be an admissible heuristic. Suppose we want to ...
1
vote
1answer
40 views
Why we don't consider cycles in path problems?
I'm working on my research and I found that for directed graphs, there are many algorithms trying to solve shortest path problem(like Dijkstra, Bellman‐Ford algorithm), but few is to get all paths(...
0
votes
1answer
101 views
How to prove that Bellman-Ford algorithm detects a negative cycle?
I have read that if we run the outer-loop of the Bellman-Ford algorithm for |V| times (where |V| is the number of nodes in the graph) and check if any distance has changed in the |V|th iteration (i.e. ...
1
vote
2answers
57 views
What is the shortest total path between pairs of points?
I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length ...
0
votes
0answers
21 views
Parallel Floyd-Warshall algorithm in Assembler - possible?
I want to implement parallel Floyd-Warshall algorithm in assembler.
The FW algorithm is all about if and assign statements ...
0
votes
0answers
41 views
Bellman-Ford algorithm from Éva Tardos
I am trying to understand the Bellman-Ford algorithm from Jon Kleinberg, Éva Tardos: *[Algorithm Design].
Page no: 296 The recursive equation that is written:
$$M[v]= \min(M[v], \min_{w\in V}
(c_{vw} +...
1
vote
1answer
22 views
In a set of sentences, how could I determine the fewest sentences that contains all characters?
So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced.
So ...
0
votes
0answers
36 views
Solving shortest path problem with Dijkstra’s algorithm for n negative-weight edges and no negative-weight cycle
Although many texts state Dijkstra's algorithm does not work for negative-weight edges, the modification of Dijkstra's algorithm can. Here is the algorithm to solve a single negative-weight edge ...
0
votes
1answer
264 views
Why is DFS not suited for shortest path problem?
I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know ...
0
votes
1answer
566 views
Google Foobar Level 4 - Graph Problem
So, I have been solving problems in Google Foobar for the past two weeks or so ans has reached Level 4. The first problem is as stated below and I have come up with a solution which is able to pass ...
1
vote
0answers
28 views
Finding homotopies in a 2-complex
Are there any efficient algorithms to find the shortest homotopy between two paths in a $2$-complex?
10
votes
1answer
289 views
Shortest Path in a Directed Acyclic Graph with two types of costs
I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$...
2
votes
2answers
69 views
Graph search or shortest path algorithm for graph with multiple “goals”?
I did a project in a class using A* search to solve an 8-puzzle.
But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles.
I’m not sure whether ...
1
vote
1answer
154 views
Bellman Ford Dynamic Programming
I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so ...
1
vote
1answer
69 views
Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS
I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked ...
0
votes
0answers
148 views
Removing any arbitrary vertex from a directed graph?
I came upon this particular question which I do not understand from Jeff E. Algorithms, Chapter 9, ex. 8. https://jeffe.cs.illinois.edu/teaching/algorithms/book/09-apsp.pdf
How can we remove any ...
0
votes
0answers
19 views
Dinamic programming relationships in the all-pairs shortest paths problem
CLRS includes two dynamic programming algorithms for solving the same problem: all-pairs shortest paths.
The kernels of these algorithms (side-by-side) look almost identical, except that they seem to ...
0
votes
1answer
102 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 ...
2
votes
0answers
32 views
Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph
As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
1
vote
1answer
149 views
Diameter of a disconnected graph
Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?
0
votes
2answers
49 views
Online shortest path in ordered DAG
Suppose I have an edge-weighted connected rooted DAG $G = (V, E, r \in V, w \in E \to \mathbb{Z})$ where there exists a sequence of nonempty sets (called "levels") $L_0 = \{r\}, L_1 \subset ...
1
vote
1answer
82 views
Clarification in the proof for the Bellamn-Ford algorithm
While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma:
After k (k >= 0) iterations of relaxations, for any node
u that has at least one path from s (the start ...
0
votes
1answer
70 views
Negative cycle detection using Bellman-Ford and its correctness
I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.
I have 2 doubts about the correctness of the algorithm:
Why are we ...
1
vote
1answer
55 views
Determine whether given f is shortest path function
I have the following question:
Let $G = (V,E)$ be a directed graph with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every ...
0
votes
0answers
34 views
Algorithm to calculate shortest path when updating the heaviest edge in a path [duplicate]
For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge.
$$w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...
2
votes
1answer
128 views
Modified shortest path problem
For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{...
2
votes
0answers
26 views
Is there a Dijkstra like pathfinding with condition satisfication algorithm?
Say we have a place-transition digraph system. A transition can fire if all input places have marks. A transition fires by consuming items from input places and placing one into each output place. A ...
0
votes
1answer
128 views
Create an algorithm for computing the shortest path in O(m + nlogn)
So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non ...
0
votes
1answer
128 views
find shortest paths from source to all vertices using Dijkstra’s Algorithm?
For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ???
For ...
0
votes
0answers
29 views
Bellman-Ford - If an edge was relaxed one more time then there is a cycle in parent pointers
I was given an exercise to prove that the Bellman-Ford algorithm, with maintaining a predecessor array for the vertices, allows finding a negative weight cycle in the graph.
I should emphasize that ...
1
vote
1answer
162 views
Minimum bottleneck path between two vertices in an undirected graph
I have an undirected graph, where the value of the path is the maximum weight among all weights
edges included in it. And I want find the path of minimum value between two given vertices in time $O(n ...
