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
1answer
25 views

Proving inequalities related to Dijkstra's algorithm

Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$. Define $IN(v)$ as the set of in-neighbors of $v$. Define $w(u,v)$ as the weight of the edge $(u,v)$. I am asked to ...
2
votes
1answer
90 views

Algorithm to find longest path in a tree that is smaller than x

Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any ...
2
votes
1answer
52 views

shortest path tree algorithm

Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$. I want to find an algorithm for the shortest path ...
2
votes
2answers
391 views

Given all pairs shortest paths matrix, find graph with minimum total sum of edges

I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some ...
2
votes
1answer
60 views

All pair shortest path in a tripartite graph

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
2
votes
1answer
440 views

Shortest path with a start vertex that touches all nodes at least once with repeats allowed

I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I ...
2
votes
1answer
363 views

Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms

From my understanding, a problem amenable to a dynamic programming solution has these two properties: Overlapping Subproblems — The same subcase (a subsection of the overall problem) keeps ...
2
votes
2answers
410 views

Find the minimum path to every vertex using Bellman-Ford

I was studying the chapter 24 of the CLRS and got to the following question: 24.1-5 $\star$ Let $G=(V,E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb{R}$. Give an $...
2
votes
1answer
452 views

Applying Johnson's algorithm on undirected graph with negative edge weights

Currently we are discussing applying Johnson's algorithm on undirected graph with negative edge weights. And the graph may contains cycles, but the sum of weights of any cycle is guaranteed to be non-...
2
votes
1answer
815 views

Retrieve shortest path between two nodes using Bellman-Ford-Moore algorithm sequentially

This is my first question here and I hope you can help mt clarifying a doubt. Basically, I'm studying shortest path algorithms, for instance Dijkstra, Bellman-Ford-Moore, and I came up with a doubt. ...
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 ...
2
votes
1answer
80 views

Single-source shortest path algorithm for graphs representing stacked behavior

I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG). That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent ...
2
votes
1answer
2k views

Shortest path from that passes through a set of edges once

Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big. Slow solution: Finding shortest ...
2
votes
2answers
492 views

Shortest Path Passing All Routes

Is there a shortest path algorithim that calculates the shortest route passing all available roads, ending where you started? This differs from the Travelling salesman problem as you need to pass ...
2
votes
1answer
195 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 ...
2
votes
1answer
711 views

Shortest directed path connecting given subset of vertices

Given weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$ source vertex $v \in V$ vertex subset $U \subset V$ how to find a shortest directed path from $v$ containing all vertices ...
2
votes
1answer
14 views

Performant algorithm to find edges without cross overs

I have a series of graphs with points plotted like this: Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don'...
2
votes
2answers
58 views

How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is ...
2
votes
1answer
41 views

Thorup : What is the meaning of super distance?

While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance. It says: "For each vertex we have a super distance $D(v)\geq d(v)$" $d(v)$ must ...
2
votes
1answer
61 views

Bellman-Ford - is number of interations greater than diameter?

Diameter of a connected, undirected graph is the smallest natural number d, so that between any two vertices of the graph exist path of length at most d. Prove or disprove: in Bellman-Ford is ...
2
votes
1answer
185 views

Given directed connected weighted graph, check if d(v) = delta(s,v)

I'm having some hard time with this problem. Can someone give me some clue/guidance? This is an homework question, so please don't just solve it. Given a weighted directed connected graph $G = (V,...
2
votes
1answer
52 views

Djikstra algorithm analysis

My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that? Dijkstra algorithm pseudocode: ...
2
votes
1answer
61 views

Shortest path with nodes containing collectibles of negative cost

Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible ...
2
votes
1answer
61 views

How to find MST for each source

Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost. The image bellow is an example of a possible ...
2
votes
1answer
42 views

Comparing nodes in A*

Nodes in the open list in A* will be sorted by their f-cost, but if the f-cost of two nodes are equal, will their h-costs instead be compared? I'm asking because I've seen implementations where the h-...
2
votes
1answer
113 views

LPA* implementation keeps looping

Short story I am currently trying to implement LPA* in an existing navigation system and find the algorithm seems to loop forever, expanding the same vertices over and over again. I am wondering what ...
2
votes
1answer
337 views

Conditional Shortest Path Through Weighted Cyclic Directed Graph

Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge ...
2
votes
1answer
89 views

Dijikstra implementation in books subtly different

I was reading about Dijkstra algorithm and was referring two books 1) Introduction to Algorithms by Cormen Section 24.3 2) Algorithm design by Kleignberg Section 4.4 And found a subtle difference in ...
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
1answer
53 views

Why do admissible functions allow $A^*$ to retain correct shortest path computations?

I was reading about how to use $A^*$ and was told that: A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$. I was ...
2
votes
1answer
278 views

Variation on Bellman-Ford Algorithms?

We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this ...
2
votes
1answer
348 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 $...
2
votes
1answer
88 views

Optimal path through a DAG with sparsely available edge weights [closed]

I would like to create a plot of certain metrics that are collected at revisions of a software system. The objective of the software engineers is to minimize those metrics. For version control, the ...
2
votes
1answer
226 views

Finding path with minimum weight

There is a river which can be considered as an infinitely long straight line with width W. There are A piles on the river, and B types of wooden disks are available. The location of the $i$-th pile ...
2
votes
0answers
17 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
43 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
33 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
3answers
85 views

Shortest path between any origin to any destination through some way stations

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm? You can visit those way stations ...
2
votes
0answers
168 views

Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|). I was thinking about using Bellman-Ford to solve the ...
2
votes
0answers
130 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
110 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
31 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
124 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
36 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
348 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
266 views

Analysing Dijkstra Algorithm by using different varieties of Data Structure

Question I want to analyse Dijkstra Algorithm by using different varieties of Data Structure. My solution Adjacency matrix to Store the Graph and Binary heap for Priority Queue. $...
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
194 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
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 ...