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
607 views

What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

I am looking for the most efficient algorithm for finding shortest path between two Vertices. The graph is: undirected edge-weighted Non-negative less then 300 nodes I understand that most of the ...
2
votes
1answer
339 views

How does Hassin's algorithm for the Restricted Shortest Path work?

I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds $...
1
vote
2answers
2k views

How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time. But in this case, we can't track actual shortest path with ...
2
votes
0answers
555 views

Does dijkstra works when I multiply weights of successive nodes

Consider a complete bidirectional weighted graph. Weight of each edge (a,b) is the probability of getting from a to b. So all weights are in range (0,1]. Probability of going from ...
1
vote
1answer
876 views

Shortest path that visits maximum number of strongly connected components

Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits ...
4
votes
0answers
124 views

Successive Shortest Paths vs Ford–Fulkerson

Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page ...
4
votes
1answer
958 views

All pairwise shortest paths in a graph: does knowing the path weights help?

This question concerns the all-pairs shortest paths (APSP) problem (where we are given a graph with edge $(i,j)$ given weight $w_{i,j}$ by the distances between the two nodes $i$ and $j$, and where we ...
3
votes
2answers
522 views

Shortest Path Variant (constrained max hop)

INPUT: directed non negative weighted graph, s, t, k OUTPUT: SSSP from s to t where the path has $\leq k$ vertices MY PROGRESS: ...
5
votes
2answers
2k views

Recalculating shortest path after changing the weights

I have a weighted, directed graph. I do the following. Given nodes $s$ and $t$ I compute shortest path. Then, I decrease weights of some edges and want to see if there is now another shortest path. Of ...
2
votes
1answer
997 views

How to find all shortest paths between two nodes in a weighted undirected graph? [closed]

How to find all shortest paths between node 1 and N in a weighted undirected graph? There can be multiple edges between two nodes. I want to find all nodes that can be on a shortest path. For example:...
1
vote
2answers
204 views

Delay Constrained Shortest Path in $O(D \cdot |E|)$ time

I have the following homework exercise: We are given a network $N=(G,w,d)$, $G=(V,E)$ together with a designated source node s∈V and target node $t \in V$, where $w\colon E \to Z^+$ and $d\colon ...
3
votes
2answers
394 views

All Pairs Shortest Path Fewest Stops

I have a graph with V vertices and E edges. Each edge is a road that takes fuel F to travel. I have a gas tank of capacity K, and want to find the fewest number of refills needed to go from any vertex ...
2
votes
1answer
60 views

Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?

From the analysis of Dijkstra there is a $O(mlogn)$ factor that assumes we do a decreasekey for every single edge of the given input graph. However I find it hard to come up with an instance that can ...
1
vote
1answer
951 views

Shortest-Path for Weighted Directed Bipartite Graphs

I did a research project in which I seek to move a car through zones from origin to destination. This allows for the formulation of a bipartite graph because only adjacent zones can be connected. Each ...
4
votes
1answer
305 views

Find the shortest OPEN path connecting a set of 2D points (special case)

I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered. The ...
-1
votes
1answer
128 views

Algortihm for path existence in a N by N board moving with a chess knight

I have a problem which goes like this. There is an $N$ x $N$ board in which some squares are maked with $x$. The upper left and lower right corner squares are also marked. You have a chess knight ...
2
votes
1answer
170 views

Do we want largest or smallest priority in the A* algorithm?

On this site http://algs4.cs.princeton.edu/25applications/ is described A* algothihm this way The A* algorithm is a problem-solving process where we put the start configuration on the priority ...
4
votes
1answer
6k views

Comparison between IDA* and Recursive best first search

How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity? Both algorithms are intended to be memory-efficient heuristic ...
2
votes
2answers
2k views

Delivery Algorithm - Find shortest paths

Given - A center(lat=x,lng=y) 'C' from which a delivery boy makes a round trip. A delivery boy has a bag which may contain at the most 10 boxes to deliver. A set of points Di (lat=xi,lng=yi) ...
3
votes
0answers
408 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{...
4
votes
1answer
3k views

What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
0
votes
2answers
484 views

Existence of shortest path in a graph with no negative cycles?

Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex. How do I prove that for every ...
1
vote
1answer
125 views

Shortest Path problem(Single Source&Destination) [closed]

Given: A completely connected directed acyclic graph. What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes? Constraint: 1)The result ...
2
votes
2answers
806 views

Find all the paths from node A to node B

You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the bottom ...
1
vote
1answer
2k views

Computing the k shortest edge-disjoint paths on a weighted graph

Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty. We could use Dijkstra to find the 1st "disjoint" (edge ...
3
votes
0answers
303 views

Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial ...
3
votes
1answer
1k views

Algorithm to find all paths of length k

Consider the following definition of 3-friends: person 1 is 3-friends with person 2 if they are direct friends or person 1 is friends with a friend of person 2 or person 1 is friends with a friend ...
1
vote
0answers
103 views

How do I apply a single iteration of Floyd's algorithm to an adjacency matrix? [closed]

I have the following adjacency matrix for a graph with nodes {a,b,c,d}: \begin{bmatrix} & & a& b& c& d\\ & & & & & \\ a& & 0& 1&...
0
votes
1answer
3k views

Best pathfinding algorithm for undirected unweighted graph [closed]

I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the ...
2
votes
1answer
100 views

Why can't edit distance be solved as L1 distance?

Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to ...
1
vote
0answers
22 views

Finding next lightest path [duplicate]

Using Dijkstra algorithm, how can I find the next shortest path in a directed weighted graph? (When saying next, I mean that the next path must be heavier than the lightest path and not equal). The ...
0
votes
1answer
150 views

Application of shortest vertex-disjoint path with time window

I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to ...
0
votes
1answer
2k views

Normalizing edge weights and the effect on Dijkstra's algorithm [duplicate]

If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would ...
1
vote
0answers
129 views

Weighted, Acyclic Graph and Change Weights Problem?

I ran into a question as follows: We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with ...
3
votes
1answer
878 views

Shortest paths in weighted graphs, and minimum spanning trees

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
1
vote
0answers
101 views

Fully dynamic k-shortest-path

I have a directed acyclic graph with positive edge weights. It is constantly changing in that nodes are deleted and added. For each change, I need to find the $k$ shortest paths. My current approach ...
5
votes
1answer
1k views

Bellman-Ford Termination when there is no change on vertex weights?

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the ...
0
votes
1answer
863 views

Shortest path in a matrix

I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each ...
1
vote
0answers
56 views

How to convert a search solution to a path to be tracked?

Let's say I have a space with obstacles and I'm trying to control a robot's movement while avoiding obstacles. I also have a start state and a goal state. I use a search algorithm to find the shortest ...
3
votes
1answer
320 views

Shortest path in a mutable graph

I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find any shortest path to every other node from a root $s$. This is performed in time proportional to $...
3
votes
2answers
396 views

Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
6
votes
0answers
998 views

Suurballe's Algorithm: Proof of Correctness

I was reading about Suurballe's algorithm on Wikipedia, for the shortest edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
4
votes
2answers
13k views

Is there an algorithm to find all the shortest paths between two nodes?

Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes. What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all ...
1
vote
2answers
215 views

Shortest path where weights are computationally expensive to calculate

Suppose we have a function, CalculateEdgeWeight, which is computationally expensive. We want to find the shortest path between two nodes $s$ and $t$ in a simple edge-weighted digraph $G= (V,E)$ where ...
1
vote
1answer
1k views

Algorithm to find shortest path between two nodes

I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint. The additional constraint is that ...
3
votes
1answer
496 views

Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} \...
1
vote
1answer
740 views

Shortest walk that covers $k$ nodes

I have the following problem, I would like to know an efficient algorithm to solve it. Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex $s$...
3
votes
1answer
326 views

kth nearest vertex in a unweighted graph

Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of special vertices and an integer $k$, I want to find the $k$th nearest special vertex for each vertex. What algorithm ...
0
votes
1answer
418 views

Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in $...
5
votes
2answers
3k views

Algorithms: Difference Constraints

I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem: Consider the following set of difference constraints: ...