Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
1k views

Shortest path with positive edge cycle

When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their ...
1
vote
0answers
294 views

Shortest path with minimal blue edges

Let $G=(V,E)$ be an undirected graph,such that ever $e\in E$ has a color-blue or red. Given $G$ and some $s,t\in V$ ,find an efficient algorithm that find from all pathes from $s$ to $t$,one with ...
0
votes
1answer
90 views

Is it possible that the diameter of a graph be shorter than the longest shortest path?

I used networkx to find the diameter of a graph that I have. It gave a diameter of 4. However, I found that between two particular nodes, using networkx's shortest path function, the path length is 5. ...
2
votes
1answer
514 views

Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges

I know that this doesn't work because shortest path with a lot of edges may have bigger weight than a longer path with less edges. But what if, you keep track of the edges that our current weight path ...
1
vote
1answer
103 views

Prove that every two vertices in graph are connected by a path of some length

I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning. Every node in ...
1
vote
0answers
2k views

How to backtrack the shortest path in BFS based shortest path calculation? [closed]

I understand how BFS can give the shortest path in a graph but I am not able to code the entire thing. The part where I am stuck is when I pop a node from the queue and see that its the target node, ...
1
vote
2answers
194 views

Sum of all distances in connected DAG in $O(n\log n)$

I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows: For every node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are ...
4
votes
2answers
3k views

Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding ...
4
votes
1answer
289 views

Looking for an algorithm to find a shortest path in a special graph

I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special ...
1
vote
2answers
1k views

Finding the Shortest Path that connects k nodes in a graph

I was wondering if there are algorithms for finding the shortest path that contains some selected $k$ nodes in a weighted graph. More specifically, the path that we are looking for needs to pass ...
1
vote
1answer
65 views

Shortest past including an edge from a given set

I am working on the following problem. There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find ...
1
vote
0answers
51 views

Pathfinding when the graph varies over time

Let's say I want to simulate a very large number of travelers booking flights. For example, a traveler might want to fly from New York to New Delhi. There's no direct flight from New York to New Delhi,...
3
votes
1answer
940 views

Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP): \begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le ...
0
votes
1answer
98 views

Combining Runtime Complexity Expressions with respect to Dijkstra

If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem after running Dijkstra twice (outside the loop), I think I get the following runtime complexity ...
1
vote
0answers
502 views

Edge weight changing during execution in shortest path algorithm

I have an undirected graph with weighted edges, in which I want to find the shortest paths from an initial node to every other node. Obviously Dijkstra's algorithm is usually a good choice, and I have ...
1
vote
0answers
149 views

State-of-the-Art techniques on dynamic shortest path computations

Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target ...
1
vote
1answer
468 views

Bellman-Ford: Find all nodes that have minus infinite distance to source

Given a weighted, directed graph (V, E) may contains some negative cycles and a source node s, I would like to know for all node ...
2
votes
0answers
394 views

Algorithm to traverse all unblocked $1*1$ squares in a $n*m$ grid

Given a $n*m$ grid, some $1*1$ squares are blocked(can't be entered) and some are unblocked(can be entered). What is the algorithm which prints the shortest path, such that the path covers all ...
4
votes
2answers
2k views

Minimum-weight shortest-path tree

How can we compute the shortest-path tree of minimum total weight for a given connected graph? I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one ...
0
votes
0answers
66 views

Adapting Dijkstra to list all shortest paths [duplicate]

I found a code in the internet for Dijkstra's shortest path algorithm in PHP. The problem is it only shows one possible path. If there are several paths having the same distance, it only outputs one ...
1
vote
1answer
421 views

Running Time of naive implementation of Dijkstra's Algorithm

Here is the "naive" implementation of Dijkstra's algorithm that the professor uses: For a directed graph $G = (V,E)$ as input Initialize: $X = \{s\}$ (the vertices processed so far) ...
3
votes
2answers
330 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
780 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
157 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
307 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
770 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
78 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
299 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
144 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
448 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
351 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
17 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
321 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
367 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
79 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
324 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
10k 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
246 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
956 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
556 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
139 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 ...