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.

658 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
• 1
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 ...
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,...
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. ...
• 101
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 ...
8 views

• 532
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})$ : \label{eq:1} \underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\sum_{(i,j)\in\...
• 51
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 : \label{eq:1} \underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\...
• 51
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 ...
• 149
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 ...
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 ...
1 vote
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?
• 152
1 vote
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 ...
• 257
1 vote
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 ...
• 111
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 ...
• 47
1 vote
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 ...
• 11
1 vote
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 ...
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 ...
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 ...
• 1
1 vote
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 ...
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. ...
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 ...
• 69
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 ...
• 13
1 vote
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 ...
• 457
1 vote
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 ...
• 111
1 vote
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. ...
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 ...
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/...
1 vote
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 ...
• 149
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 ...
• 131
1 vote