# Questions tagged [shortest-path]

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

496 questions
Filter by
Sorted by
Tagged with
18 views

### Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees

I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [...
57 views

### Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
35 views

### Given complete graph, find optimal path with two costs on each edge

We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of ...
147 views

### Why is it true that given a monotonic heuristic function, A* can be seen as Dijkstra's algorithm where no node needs to be processed more than once?

Maybe I am missing something very easy and obvious. But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: ...
128 views

### Shortest route through ordered points

My algorithm-fu is really weak and I do not know how to express following problem in terms of any other problem known to me: Given a small rectilinear grid and coordinates of four cells in this grid (...
32 views

### Travelling Problem with Constraints

Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance. You start your travel at a given node, say $1$, and end ...
131 views

### Shortest path from one source which goes through N edges [closed]

In my economics research I am currently dealing with a specific shortest path problem: Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from ...
60 views

### IP algorithm for finding path in graph

Suppose for each positive integer $N$, we have a graph $G_N$ with $N$ vertices labelled $1$ to $N$ (so $\log N$ bits are required to specify a vertex). Suppose we have a PSPACE algorithm to determine ...
39 views

### Generating flight path for aerial photography

I need to generate the shortest possible path for aerial photography using a fixed wing unmanned air vehicle (UAV). The image below shows the area I'm going to search. The white cells are the cells I ...
377 views

### Algorithm - True shortest path for triangulated 3d-surface

I need to find true shortest path between two points. true means that shortest path can be laid both through the vertices, and through the edges. Input Set of triangles, given by coordinates of 3D-...
2k views

### Can Bellman-Ford run with time-complexity of cubic order

After reviewing the Bellman-Ford algorithm I can see that it runs with time complexity of $O(n^2)$ or, more exactly, $O(VE)$. It is necessary to loop (V-1) times the number of edges which is in fact 2 ...
205 views

### Why Johnson’s algorithm for all pairs shortest paths may create negative cycle?

There is a contradiction in the Johnson’s algorithm presented in CLRS edition 3 page 700 that I can't understand. Johnson’s algorithm uses the technique of reweighting, which works as follows: for ...
476 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 ...
410 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 ...
263 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 ...
971 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 ...
397 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 ...
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-...
590 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 ...
47 views

### Maze with constraint on grid [duplicate]

There are some algorithm or solving a simple maze on the web; but what I am trying to solve is a bit more complicated. Here is an example: ...
163 views

### Update SSSPP solution on complete digraph on weight changes

I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative. On various occasions '...
147 views

### Multicommodity shortest path problem on a directed acyclic graph

I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
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 ...
253 views

### Shortest paths candidate

Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. ...
1k 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? ...
131 views

### Path on an edge-colored DAG using exactly $k$ colors

I have the following problem: Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$, does there exist a path from $s$ to $t$ using exactly $k$ ...
1k views

### Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms

The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford ...
225 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 ...
407 views

### Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
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 ...
1k views

### Find least probable path in graph

I am working on a special case of the longest path problem. For a cyclic directed graph $G=(V, E)$, where the edge-weights are probability values (i.e., $P(\_) = w(s, q)$ with $s,q \in V$), my aim is ...
76 views

### Determine shortest path in a 4x5 grid graph

Suppose we had a graph $G = (V,E)$. This graph can also be seen as a $4x5$ grid graph as shown in the image. There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and ...
270 views

### Shortest path from source to all vertices, but with some wildcards

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer). You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
661 views

### Time complexity of Dijkstra's algorithm for sparse graph

I'm not sure I understand the answer to this question: Question 9. What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, ...
238 views

### Increasing every starting edge by a constant, then the shortest path tree remains the same?

Consider a directed graph G = (V,E) with non-negative costs on each edge. With s being a starting vertex. Prove that by adding ...
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 ...
620 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 ...
980 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 ...
140 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 ...
3k 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 ...
156 views

### Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths. An example is if we have ...
27 views

### Dijikstra's algorithm with “hull” value catch

Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here. Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, ...
63 views

### What's the best algorithm to find the shortest path between 2 vertices in a graph?

Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?
190 views

### How does the slow All-pairs-shortest-paths algorithm work?

I am trying to fully understand the following algorithm from CLRS book: I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. ...
159 views

### Shortest Path in Layerwise Complete Graph

Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. ...
387 views

### Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
494 views

### Floyd–Warshall algorithm on an undirected graph contains negative weight edges

According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances ...