Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
5
votes
2answers
2k views

Shortest path between 2 vertices using at most K edges using Bellman-Ford

I'm a bit confused about stopping at Kth iteration on the Bellman-Ford algorithm to find the shortest path of at most length k from s to t. Let me show you a graph and explain you what I understand: ...
3
votes
1answer
328 views

Finding trading cycles

Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example, person 1 has item A, C, D, and wants item F person 2 has item B, C, and wants E ...
2
votes
1answer
4k views

Single-Source Shortest Path with at most k edges using Dijkstra's algorithm

I am trying to solve a bounded SSSP problem as follows: Given a connected weighted graph with non-negative edges (might have cycles), find the shortest path from a vertex s to a vertex t with ...
2
votes
0answers
399 views

Bhandari Algorithm: Canceling Edges

I have a quick question on implementing the Bhandari algorithm. I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for ...
3
votes
0answers
84 views

Shortest paths in isomorphic graphs with different edge weights

I'm looking for a way to find the shortest paths from a source to all destinations in isomorphic undirected graphs with different edge weights. The only thing I can think of is using Dijkstra on each ...
3
votes
1answer
2k views

Can I run Dijkstra's algorithm using priority queue?

I think I can run Dijkstra's algorithm using any data structure. I do not see any implementation details of Dijkstra's algorithm. Is a priority queue a possible data structure? Will running Dijkstra'...
4
votes
1answer
350 views

Can a shortest-path tree be a also maximum spanning tree?

If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example! I ...
12
votes
1answer
11k views

How does consistency imply that a heuristic is also admissible?

A heuristic function $h (n)$ is... Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the ...
2
votes
0answers
255 views

node-disjoint k-shortest path

As part of an object tracking application, I am trying to solve a node-disjoint k-shortest path problem. My graph is (for now) k-partite. I have a single source and single sink. My edges are initially ...
5
votes
1answer
151 views

K shortest paths - any relation between K and % of graph nodes in discovered paths?

Let's say I have a graph with $N$ nodes, $A$ arcs and an average branching factor $b$. I want to find the $K$ shortest paths between two nodes. Is there some relation (even approximate is fine) that ...
2
votes
1answer
963 views

AI: Heuristic function A* search

I have an assignment in my university where I have to implement Uniform Cost Search and A* Search. We have an input which includes a map and queries. The map is weighted, directed graph, represented ...
9
votes
1answer
582 views

Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map): positively weighted undirected sparse with about 100 nodes My ...
0
votes
1answer
2k views

Shortest path algorithm using Dijkstra with Fibonacci heap

Given an undirected connected graph $G=(V,E)$ with positive weights, where $|V|>2009$, and each vertex is of degree of at most $10$. Give an efficient algorithm to find the $2009$ closest nodes to ...
3
votes
1answer
143 views

Early termination of A* with weak heuristic if solution is known

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent. Suppose I already know of a path ...
3
votes
1answer
1k views

Is it possible to produce different shortest path trees using bellman ford and Dijkstra algorithm?

Given a graph G=(V,E) with positive edges weights, Is it possible to produce different shortest path trees for the Bellman-Ford algorithm and Dijkstra's algorithm?
1
vote
2answers
527 views

modify Dijkstra's algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

i want to modify Dijkstra algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex I tried it with BFS(breadth first search). Initially ...
2
votes
1answer
221 views

Linear time algorithm for finding $k$ shortest paths in unweighted graphs

Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the ...
8
votes
1answer
865 views

Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
0
votes
0answers
478 views

Fastest Algorithm to find shortest path between two edges in a graph

If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)? I am trying to answer a question in the EPI book. ...
-2
votes
1answer
588 views

Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ...
2
votes
1answer
72 views

Qualifications for a problem to be solved as a single source shortest path problem

What are the pre-conditions for any problem X to be qualified for being solved in a single source shortest path problem (SSSP) setting? Lets, say we have a problem X. What should be the pre-...
4
votes
2answers
567 views

Dijkstra with bitwise OR of edge costs

Given a graph $G$ where loops and multiple edges are allowed. A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost $$ cost = e_1 | e_2 |...|e_k$$ where $|$ is the bitwise OR. Assume for all ...
2
votes
1answer
84 views

Single-source shortest path algorithm for graphs representing stacked behavior

I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG). That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent ...
2
votes
1answer
177 views

Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?

I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum ...
0
votes
1answer
392 views

Shortest distance from a set of points

Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$. To ...
2
votes
0answers
387 views

Vectorized Algorithm for finding the Shortest Path in a Graph

I know that you can calculate the shortest path in a vectorized fashion using Floyd-Warshall, e.g. like proposed by Han and Kang, however I want the matrix, they call "via", the actual route taken ...
2
votes
1answer
2k views

Shortest path from that passes through a set of edges once

Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big. Slow solution: Finding shortest ...
11
votes
0answers
530 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
0
votes
1answer
5k views

Complexity of the Dijkstra algorithm

I'm little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I ...
4
votes
0answers
149 views

MST that contains a shortest $s,t$-path

Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$...
5
votes
0answers
84 views

Find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance. ...
0
votes
1answer
315 views

Find all shortest paths in a graph where path has even number of edges and greater than 6

Let $G=(V,E)$, a directed with non-negative weights ($w:E\to\mathbb{R}^+$). Describe an algorithm, finds all shortest paths in the graph from a source vertex, $s\in V$, such that, each paths has an ...
1
vote
3answers
982 views

Understanding Dijkstra's algorithms

As far as I understand, Dijkstra's algorithm always picks the nearest neighbour. But how does it work for the following graph? ...
1
vote
1answer
772 views

Algorithm to find a path connecting given nodes in a graph

Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for ...
0
votes
1answer
549 views

Why does Dijkstra's algorithm not account for updating node distances after expanding a node?

Why does Dijkstra's algorithm not re-evaluate/re-expand nodes who have been expanded and later had their weight changed? For example, in the accepted answer of this question (link), if the algorithm ...
9
votes
2answers
13k views

A* graph search time-complexity

Some confusion about time-complexity and A*. According to A* Wiki the time-complexity is exponential in the depth of the solution (shortest path): The time complexity of A* depends on the ...
1
vote
1answer
88 views

Partial path known in Single source shortest path problem

I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path. If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal ...
3
votes
1answer
484 views

Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...
4
votes
2answers
407 views

Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...
2
votes
1answer
56 views

Why do admissible functions allow $A^*$ to retain correct shortest path computations?

I was reading about how to use $A^*$ and was told that: A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$. I was ...
3
votes
3answers
1k views

Ideal value of d in a d-ary heap for Dijkstra's algorithm

I stumbled upon the following statement: By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time ...
-2
votes
1answer
104 views

Shortest path with no two consecutive edges from a certain edge set

Given a graph with nodes $N$ and two sets of edges $E_1$, $E_2$ where no two edges from $E_2$ can be used consecutively, find the shortest path between $n_1, n_2 \in N$. Is there a smart way to ...
15
votes
4answers
6k views

Dijkstra's algorithm on huge graphs

I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to ...
2
votes
1answer
1k views

finding shortest negative cycle

Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the shortest (uses the least number of edges) negative weight cycle in the graph? I know that I can ...
5
votes
1answer
635 views

Finding the lowest-weight negative cycle in a weighted digraph

Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible? I know that I can detect ...
-2
votes
2answers
507 views

When is bidirectional search unusable?

Is there any situation that bidirectional search on a graph is not applicable? for example is there any classes of graph that we can only use ordinary Dijkstra's algorithm, and can not use its ...
1
vote
1answer
870 views

Monotone property of heuristic in $A^*$ algorithm

In the $A^*$ algorithm, the optimality of the path is guaranteed when the heuristic has the property of being admissible or monotone\consistent. I was able to understand the admissible property, ...
5
votes
1answer
1k views

Is the “Bidirectional Dijkstra” algorithm optimal?

In some sites they say the bidirectional Dijkstra's algorithm is optimal, e.g., this, and this. Also there is some software that uses this algorithm (for example this DBMS). But some posts express ...
2
votes
2answers
528 views

Shortest Path Passing All Routes

Is there a shortest path algorithim that calculates the shortest route passing all available roads, ending where you started? This differs from the Travelling salesman problem as you need to pass ...
2
votes
0answers
60 views

How to compare A* with DP approach in finding shortest Path?

Consider a hypercube defined over $n$ dimensions where the edges are associated to strictly positive weights, and nodes are marked with $n$ bit-strings, e.g. the source is marked as (0,0,0) in a 3-...

1 4 5 6 7 8 10