A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
53 views

How to avoid looping of packets while implementing k-shortest paths algorithm in Network Simulator-3?

I am trying to implement k-shortest paths algorithm in NS-3 for IPv4GlobalRoutingProtocol. I am concerned about how to avoid looping of packets. My implementation calculates k-shortest paths from ...
11
votes
2answers
4k views

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive. the algo depends on finding a new weight function (w') that ...
0
votes
1answer
1k views

Brandes' betweenness algorithm for weighted undirected graph

I am studying Brandes' betweenness algorithm for weighted undirected graph. I am not sure that, in Algorithm 1 (which is based on Dijkstra's shortest path algorithm), If a node is first encountered, ...
7
votes
1answer
2k views

How to find the shortest path from some vertex in set $S$ to set $S'$

If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That ...
5
votes
1answer
541 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
2
votes
1answer
196 views

Connecting an unconnected forest of subtrees in a graph?

If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other. What is the best way to connect these three trees such that ...
4
votes
1answer
523 views

Algorithm to find the shortest walk with k leaf nodes on a tree

Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root? Passing through a node/...
3
votes
2answers
1k views

Algorithm to find shortest lightest path in a graph from source

Given a directed graph $ G = (V,E)$ with non-negative(zero and positive) weights on the edges, and a vertex $ s \in V $ Problem: Find the lightest path from $s $ to each and every vertex $v \in V$ ...
-1
votes
1answer
24 views

What algorithm to apply when a graph have cycles (“circuits”) and some negatives values in order to find the shortest path from $x1$ to all vertices?

What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices? For instance in the following graph? I know I can'...
2
votes
1answer
4k views

Algorithm A vs Algorithm A*: What's the difference?

I can find quite a bit of literature on A* but very little on A. What is the difference between the two search algorithms?
2
votes
1answer
420 views

When is the output of shortest path $\subset$ MST?

I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like: The shortest path $B \...
6
votes
2answers
4k views

Why do we need to run the bellman-ford algorithm for n-1 times?

I'm a little confused about the concept of the Bellman-Ford(BF) algorithm to compute the shortest path in a general graph with negative weights knowing that there are no negative cycles present. I ...
3
votes
1answer
373 views

Shortest path problem where edge weight depends on path taken

I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between ...
1
vote
1answer
613 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
352 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
578 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
896 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
129 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
979 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
548 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
1k 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
210 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
409 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
62 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
995 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
311 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
129 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
173 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
411 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
513 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
135 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 ...
3
votes
2answers
845 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
316 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
108 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
156 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
130 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
938 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 ...