Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
20 views

Finding middle vertex of tree

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G ...
user438409385's user avatar
-1 votes
1 answer
47 views

Finding negative cycles using the Bellman-Ford algorithm and a source node

I'm exploring the Bellman-Ford algorithm to detect and track negative cycles (a collection of ncycle that we can see in the implementation). I'm wondering if the ...
atos's user avatar
  • 1
0 votes
0 answers
19 views

all pairs shortes path variant [duplicate]

Let $G=(V,E) $ a directed Graph with a coloring function $F:E \to red,blue$ and a weight function $W: E \to R$ I need to find all pairs shortest path s.t. every path visits at least one red edge, or ...
user169819's user avatar
0 votes
0 answers
22 views

How can i allocate troops so as to maximize the number of bases conquered without going over a maximum time?

I have a set of bases which are connected by directed edges illustrating which bases can be attacked from any particular base. Bases have a health pool (ex: 1,000,...
paullc's user avatar
  • 1
0 votes
0 answers
9 views

Shortest path in a graph where edge weights can vary dynamically based on the path taken [duplicate]

I have a directed acyclic graph whith negative edges where edge weights can vary dynamically based on the path taken. ...
user1552545's user avatar
0 votes
1 answer
44 views

Coding the labyrinth solver

The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473 To summarize, in an unknown strongly ...
user555076's user avatar
0 votes
0 answers
8 views

Profitable sequence in a $k$-partite DAG

This question is an extension of this one. Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
40 views

Shortest paths in $k$-partite DAG

Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
37 views

Dynamic Programming as DAGs - Solution Always Shortest Path?

I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the ...
Macroxela's user avatar
1 vote
0 answers
20 views

Admissible Heuristic wiki

I couldn't understand the following part on admissible heuristic on wiki. How does it reach that they have to be equal? Admissible heuristic only says the eval needs to be equal/less than the true ...
rbtcc's user avatar
  • 11
0 votes
1 answer
38 views

Longest path of directed graph with cycle and now weights

If you have a unweighted directed graph with possible cycles, what algorithm would you use to find the longest path without visiting the same node twice? Also, there are multiple starting nodes... The ...
user2330624's user avatar
2 votes
1 answer
59 views

Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?

Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of ...
dav's user avatar
  • 123
0 votes
0 answers
28 views

Distance to specific node incremental addition

Let us say I have an empty graph G and a list of nodes N to add to the graph one-by-one. Let us say that I will have a node <...
OlorinIstari's user avatar
0 votes
1 answer
258 views

Shortest Hamiltonian Path in a Complete Graph

I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm ...
WakkaTrout's user avatar
1 vote
0 answers
239 views

The second shortest path on a directed graph [closed]

The question asks to write an algorithm using Dijkstra's algorithm with time complexity of $\Theta(|E| \log |V|)$ that find the second shortest path between $s∈V$ and $t∈V$. The farthest I managed to ...
Daniel's user avatar
  • 69
-2 votes
2 answers
209 views

Could this novel algorithm be qualified to be published in Nature or Science

I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
Shawxing Kwok's user avatar
0 votes
0 answers
21 views

JPS-like path finding algorithm that keeps a distance from the obstacles?

I am using the JPS algorithm to find the shortest path from start $S$ to goal $G$ on a binary grid where each cell can be eithe 0 (free) or 1 (obstacle). Now, I would like my algorithm to take into ...
firion's user avatar
  • 101
0 votes
0 answers
72 views

Lookup Using Path Matrix in Floyd Warshall Algorithm

How is the path matrix created by the Floyd Warshall algorithm used for path lookup? The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
Labeeb Basil's user avatar
0 votes
0 answers
34 views

Probabilistic Pathfinding

Here an interesting graph problem I've recently saw: After a heist in New York City, a group must reach Miami within a set timeframe to catch an escape boat. Their vehicle's GPS shows U.S. routes with ...
Kumar A.'s user avatar
1 vote
1 answer
252 views

Question about step in proof that predecessor subgraph forms a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS: Theorem 22.5: (Correctness of breadth-first search) Let $G = (V, E)$ be a directed or undirected graph, ...
Hugh Mann's user avatar
1 vote
0 answers
45 views

How to compute the updated shortest paths given a set of edge insertions efficiently?

Let $G = (V, E)$ be a graph with edge weights $w: E \rightarrow \mathbb{R} \cup \{\infty\}$. Let $P := \{(a_i, b_i, w_i)\}$ be a set of tuples of nodes $a_i, b_i \in V$ with shortest distance $w_i$ ...
Sebastian Schmidt's user avatar
0 votes
0 answers
39 views

Running time of variant of Dijkstra's algorithm

Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
Andrew's user avatar
  • 286
1 vote
1 answer
150 views

Solving shortest path with negative weights with linear program. What is the underlying problem we want to solve?

Let us consider a shortest path problem with weights $w_e$ for each edge $e$. It can be formulated as a (integer) linear program (ILP). \begin{align} \min \quad &\sum_{e \in E} w_e x_e \\ s.t. \...
Junyan Su's user avatar
1 vote
1 answer
154 views

Finding shortest path between two points in a polygon whose vertices are given?

A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
chausies's user avatar
  • 532
0 votes
0 answers
19 views

k-shortest paths with iso-timing constraint

I would like to solve the $k$ shortest paths on a directed graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$ : \begin{equation} \label{eq:1} \underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\sum_{(i,j)\in\...
deb2014's user avatar
  • 51
0 votes
1 answer
58 views

Shortest path problem with multiple objectives

I would like to solve a shortest path problem on a graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$, which comes to minimize : \begin{equation} \label{eq:1} \underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\...
deb2014's user avatar
  • 51
4 votes
2 answers
244 views

Single Source Shortest Path Problem with Multiple Weights Each Edge

I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p ...
Daniel's user avatar
  • 149
0 votes
0 answers
18 views

Importance of an edge regarding distances

Given a graph $G=(V,E)$ and any edge $(u,v) \in E$, let us denote by $G_{(u,v)}=(V,E\setminus\{(u,v)\})$ obtained from $G$ by removing this edge. I am interested in the difference between the average ...
Matthieu Latapy's user avatar
2 votes
0 answers
19 views

Inverted Min Cost Max Flow

I'm starting to think there's no possible solution to this problem, but before jumping to conclusions I want to confirm it with collective knowledge. Let's imagine that there's a 2D grid, where S ...
Nicolás Maier's user avatar
1 vote
0 answers
32 views

Is Dijkstra's algorithm used in cheapest airfare calculators?

Is Dijkstra's shortest-path graph algorithm used in cheapest airfare calculators like Expedia or CheapAir?
Geremia's user avatar
  • 152
1 vote
0 answers
116 views

Finding the shortest path with Bellman-Ford [duplicate]

I feel this is a basic question but have been stuck at this for days. Consider an undirected graph with positive weights on its edges. The goal is to find is to get the shortest path between any two ...
Keio203's user avatar
  • 257
1 vote
1 answer
31 views

Route planning on line segments which can be connected or not

I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am ...
GPrathap's user avatar
  • 111
0 votes
1 answer
111 views

Minimum number of skips needed for shortest path

In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $\leq W$. In our given graph there is no such path but we have the ...
Hjm's user avatar
  • 47
1 vote
1 answer
171 views

Solution for the path-finding problem which visits multiple sequences of nodes

Summary Recently I have had a path-finding puzzle that has some complex constraints (currently, I don't have any solution for this one) A 2D matrix represented the graph. The length of a path is the ...
Justin's user avatar
  • 11
1 vote
0 answers
91 views

Successive shortest paths with fixed costs and costs per unit

I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
Gabriel Rebello's user avatar
0 votes
1 answer
86 views

Dijkstra's shortest path algorithm

I am reading about algorithms to find the shortest path on a graph with one source, and I have a doubt about Dijkstra's algorithm about the negative weights on edges. In this case is Bellman-Ford ...
nat.d's user avatar
  • 1
0 votes
1 answer
112 views

find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)

We have a weighted and undirected graph. I want to find the shortest path between two vertices with Dijkstra algorithm. But in the path, the weight of the edges should be increased and decreased one ...
Amir's user avatar
  • 1
1 vote
2 answers
77 views

Shortest path algorithm on graphs with non-numerical weights

TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of ...
EatChangmyeong's user avatar
0 votes
1 answer
138 views

Intuition of Flod-Warshall shortest path algorithm

I try to wrap my head around the Floyd-Warshall algorithm, and I don't understand why the shortest path is guaranteed to be found since we check only the alternative connections up to one hop deep. ...
Karol Borkowski's user avatar
0 votes
1 answer
132 views

The solution for the all-pair shortest path problem on unweighted and undirected graph

The multi-source shortest path problem for unweighted and undirected graph is as follows: Given an unweighted and undirected graph, find the length of the shortest path between any pair of vertexes. A ...
zqq's user avatar
  • 69
0 votes
2 answers
177 views

subtract the weight of the largest edge

I have an oriented and weighted graph, and I need to find the cheapest route from source to destination. Now I have a source node A and a destination node B the cheapest path is given to me by the sum ...
ant0982's user avatar
  • 13
1 vote
1 answer
75 views

The length of the shortest $s$-$t$ path equals the maximum tension between $s$ and $t$

I am stuck at the following exercise: Consider a directed graph $G = (V, A)$ with start vertex $s ∈ V$, target vertex $t \in V$ and weights $w_{ij} \in \mathbb{R}$ for each arc $(i, j)\in A$. For any ...
3nondatur's user avatar
  • 457
1 vote
1 answer
185 views

find shortest path from single source to multiple destinations with obstacles which you can move

a formulation on an example: let's have on a grid: a position of a bee queen Q (source node), a set of positions of free cells to lay an egg E (destination nodes), and a set of positions with worker ...
Dan Oak's user avatar
  • 111
1 vote
1 answer
106 views

Implementation check for Kruskal's algorithm used for maze generation

I have a pathfinding project and I want to use Kruskal's algorithm as a maze generator. I am using a rank-based disjoint set data structure to detect cycles, which seems to be the standard way. ...
disguisedtoast's user avatar
0 votes
1 answer
474 views

Does order of elements in a set matter in Dijkstra's Algorithm?

When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
Rasmus IN's user avatar
0 votes
2 answers
467 views

Calculate shortest cycle that contains node $s$

Let $ G(V, E, w)$ be a graph with no negative weights. Describe an algorithm that returns the shortest cycle containing a node $ v $. I came across this algorithm https://courses.engr.illinois.edu/...
Danny Blozrov's user avatar
1 vote
1 answer
250 views

Algorithm to compute cheapest path between two pixels in an image

I need to compute the cheapest path between two pixels in an image. The travel cost is specified by the user, and may depend on the distance between the pixels (including pixel values, which is ...
user877329's user avatar
0 votes
1 answer
360 views

Any-goal bidirectional A* pathfinding reference

I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that ...
lisyarus's user avatar
  • 131
1 vote
1 answer
144 views

Correctness of bft resulting in shortest path

I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path: source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf The ...
Tryer outer's user avatar
0 votes
2 answers
472 views

Find a simple path from S to T in a directed graph so that the product of its weights is maximum

I'm looking for an algorithm that finds a simple path from S to T in a directed graph (which might have cycles) so that the product of edge weights in the path is maximum. All the edge weights of the ...
phqb's user avatar
  • 133

1
2 3 4 5
14