Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
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 [...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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: $$...
2
votes
0answers
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 (...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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-...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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-...
2
votes
0answers
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 ...
2
votes
0answers
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: ...
2
votes
0answers
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 '...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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. ...
1
vote
3answers
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? ...
1
vote
1answer
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$ ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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)$, ...
1
vote
1answer
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 ...
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
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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$, ...
1
vote
3answers
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?
1
vote
1answer
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. ...
1
vote
1answer
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$. ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
35 views

How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility?

Recap to the Johnson's shortest path algorithm: By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \{s\}, E^\prime = E\ \cup \{(s, v)\ |\ \forall v \in ...
1
vote
1answer
50 views

What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?

I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the ...
1
vote
2answers
71 views

Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...

1
4 5
6
7 8
10