Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
3
votes
2answers
291 views

Optimality in multi-agent multi-target path finding

Suppose I have a regular rectangular weighted grid with multiple agents and obstacles. Agents cannot be in grid sites that contain obstacles, and for simplicity assume multiple agents can be in the ...
-1
votes
1answer
1k views

All Pairs Shortest Path vs Shortest Path [closed]

I do not understand the difference between the All Pairs Shortest Path problem (solved by the Floyd–Warshall algorithm) and the Shortest Path problem (solved by Dijkstra's algorithm).
6
votes
2answers
1k views

Shortest walk through a given subset of edges

Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once? I'd like to know if there is a general approach to this ...
0
votes
3answers
682 views

Modification of Dijkstra's algorithm

How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality? There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough ...
0
votes
0answers
127 views

Trouble implementing back-tracking in RBFS

I'm trying to implement an rbfs search algorithm for the 15 puzzle (pseudo code below). link to the paper where i found the pseudo code: https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/viewFile/...
5
votes
1answer
292 views

Mean and median distance in unweighted graph

I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds. The graph is an unweighted directed strongly connected graph. I ...
1
vote
0answers
700 views

Correctness of Dijkstra's algorithm

This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661). The proof makes a case that considering path $...
5
votes
2answers
1k views

Shortest path between two points with n hops

Is there an efficient algorithm which computes the (possibly approximately) shortest $n$-edge path between two points $A$ and $B$ in a weighted complete graph? Dijkstra won't work because it will just ...
4
votes
1answer
2k views

Proving that the shortest path problem between two vertices $s$ and $t$ in a graph is NP-complete

How to show that the Shortest path problem between two vertices $s$ and $t$ (finding a minimum weighted path between $s$ and $t$) in a graph is NP-complete? I received the following prof in ...
3
votes
1answer
76 views

Sampling maximal shortest paths in a graph?

Let S be the set of all possible shortest paths in a directed graph. A path s in S is said to be maximal if it is not a subpath of another path in S i.e. it cannot be extended to another shortest path....
0
votes
0answers
285 views

Shortest path in unweighted graph using an iterator only

I want to find the shortest path (least number of edges) between two nodes in an unweighted graph. How do I implement this by using a BFSiterator(v) which returns ...
2
votes
1answer
128 views

Complexity of finding the shortest simple even s-t-path

Consider a graph $G=(V,E)$ and two vertices $s,t$. What is the complexity of finding the length of the shortest simple $s-t$ path that has even length? Does the problem become harder if the ...
2
votes
0answers
412 views

Online version of bellman-ford algorithm?

Suppose I have a graph on which I've run the Bellman-Ford algorithm. Now I change the weight of subset of edges. Is there an efficient way to re-run the algorithm without having to completely start ...
4
votes
2answers
333 views

Complexity of shortest paths if paths have to use edges from different partitions

We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully ...
1
vote
0answers
16 views

Optimal linking in synchronous environment for shortest path tree problem

I am dealing with the Shortest path tree problem in the specific synchronous environment. In the following algorithm, initiator begin the execution calling primitives ...
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
319 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
3k 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
306 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
78 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
1k 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
297 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
9k 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
228 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
148 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
942 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
455 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
130 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
463 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
199 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
792 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
465 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
519 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
486 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
75 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
152 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
230 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 ...
3
votes
0answers
337 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
485 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
4k 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
129 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
83 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
215 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
878 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
670 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
443 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 ...