Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
4
votes
2answers
194 views

Graph Algorithm (Modification on Dijkstra?) : Tech Interview

Problem: Suppose we had a directed graph $G(V,E)$ with strictly positive edge weights, a nonempty set $A$ (special vertices) such that $A \subseteq V$, a positive integer $C$, and a starting vertex $S ...
1
vote
1answer
177 views

Largest possible cost of a shortest path in which every edge's length is either -1, 0, or 1

I'm doing an online course in which I'm struggling with the following (multiple-choice) question: Suppose we run the FLoyd-Warshall algorithm on a directed graph $G =(V,E)$ in which every edge's ...
1
vote
1answer
409 views

Shortest paths when edge weight depends on previous edge

I have a directed graph with non-negative weights on the edges. I can divide the nodes in two "classes", X (roughly 1700 nodes) and Y (~300). I want to collect all the shortest paths from x in X to y ...
1
vote
1answer
189 views

Shortest Path using at most k colors

I have an edge-colored network, in which edges also have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the ...
1
vote
1answer
72 views

Movement on Labyrinth with Best First Search

I have the following labyrinth where R is the robot(the parent node), red blocks are the obstacles where the R cannot move and <...
2
votes
0answers
233 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. $...
1
vote
0answers
44 views

DAG Shortest Path — original citation for academic paper

I am writing to see if someone can point me to the original citation (assuming that a single work can be pointed to) for the single-source shortest path problem in directed-acyclic graphs (DAGs). ...
3
votes
1answer
31 views

When talking about the length of a path in a graph, what exactly is a skip?

I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips? One website defines it as the ability to change the weight of one edge ...
7
votes
0answers
177 views

Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
0
votes
0answers
478 views

Algorithm to find a low cost path that visits specific nodes in a graph

How to find the minimum (or close to minimum) cost path that visits a subset of nodes within a graph? What algorithms can I use? I googled and found: http://lcm.csa.iisc.ernet.in/dsa/node181.html ...
4
votes
1answer
669 views

A recursive solution to the all-pairs shortest-paths problem

I am learning All pair Shortest Path from CLRS book,but got stuck in the begining itself.I am writing my query. According to one of the Lemma of shortest path -: All Subpaths of shortest path are ...
6
votes
1answer
93 views

Min spanning tree that preserves total weight of original graph

I have a directed, weighted graph with no double edges. Each node represents a person, and each edge represents a debt. I want to reduce the total number of transactions required to settle all debt, i....
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 ...
6
votes
1answer
246 views

Building vertex-edge visibility graph among polygonal obstacles on 2d plane

I want to implement algorithm for computing vertex-edge visibility graph among polygonal obstacles, but I can't find any description or scientific paper describing such algorithm. Currently I ...
3
votes
1answer
151 views

Shortest Path in a Graph with Interacting Edge Weights

Suppose we have a graph $G = (V,E)$. Every edge $e \in E$ has a unary cost $f(e) > 0$. Also, for every two edges $e_1,e_2 \in E$ we have a binary reward function $g(e_1,e_2) \geq 0$. Given two ...
0
votes
1answer
171 views

How to tell if a spanning tree is a shortest-spanning tree of a DAG?

I know how to calculate the shortest paths from source s to all other reachable vertices in a DAG (with no negative weight on the edges) By iterating the ...
5
votes
1answer
1k views

Finding shortest paths in undirected graphs with possibly negative edge weights

The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge ...
2
votes
1answer
651 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. ...
1
vote
1answer
265 views

Shortest paths among two subsets of nodes

Given a directed graph $G = (V, E)$ with all edge weights being non-negative and two disjoint subsets of nodes $S, T \subseteq V$, design an algorithm to find the shortest paths among $S$ and $T$, (...
0
votes
1answer
134 views

Is this a correct description of Dijkstra's algorithm

I am on a journey understanding Dijkstra's algorithm. My familiarity with mathematical terms is not great, so I have put the algorithm into my own English. I understand this is not ideal, but this is ...
0
votes
1answer
89 views

Confirmation of Dijsktra application explanation

Please can someone confirm that my description of the application of Dijkstra's algorithm is correct for this graph? ...
3
votes
2answers
151 views

Which graph algorithm should I use?

I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time ...
2
votes
0answers
171 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 ...
0
votes
1answer
31 views

What am I missing in this application of Dijkstra?

When running Dijkstra against the following graph: 1 3 A -- B -- C \ / 2 \ / 1 \ / D ...I come up with the following: ...
1
vote
1answer
216 views

Shortest path tree from each vertex implies a unique MST?

Given a connected, undirected graph G, edge-weighted (positive), prove that If G has a spanning tree T which, for each vertex r in G, is a shortest path tree from r, then G has a unique MST. I know ...
3
votes
2answers
741 views

Why can we drop the superscripts in the Floyd Warshall algorithm?

In the lecture notes, our professor mentioned that we can take down the space taken by the FW algorithm from $O(n^3)$ to $O(n^2)$ by dropping all the superscripts in the matrices (i.e. use one $n\...
5
votes
2answers
858 views

Data structure for A*'s “open” set

I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet ...
0
votes
2answers
346 views

Can Inverse of weights(1/weight,not negation) be used to find the longest path between two points by using dijkstra's algorithm?

Considering that there no cycles in the graph. I have seen the posts where the negation of the weights is suggested and to use Bellman-ford. But I was wondering if the inverse is possible.
2
votes
1answer
87 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 ...
1
vote
1answer
1k views

Shortest path with positive edge cycle

When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their ...
1
vote
0answers
248 views

Shortest path with minimal blue edges

Let $G=(V,E)$ be an undirected graph,such that ever $e\in E$ has a color-blue or red. Given $G$ and some $s,t\in V$ ,find an efficient algorithm that find from all pathes from $s$ to $t$,one with ...
0
votes
1answer
79 views

Is it possible that the diameter of a graph be shorter than the longest shortest path?

I used networkx to find the diameter of a graph that I have. It gave a diameter of 4. However, I found that between two particular nodes, using networkx's shortest path function, the path length is 5. ...
2
votes
1answer
453 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 ...
1
vote
1answer
100 views

Prove that every two vertices in graph are connected by a path of some length

I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning. Every node in ...
1
vote
0answers
2k views

How to backtrack the shortest path in BFS based shortest path calculation? [closed]

I understand how BFS can give the shortest path in a graph but I am not able to code the entire thing. The part where I am stuck is when I pop a node from the queue and see that its the target node, ...
1
vote
2answers
162 views

Sum of all distances in connected DAG in $O(n\log n)$

I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows: For every node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are ...
4
votes
2answers
2k views

Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding ...
4
votes
1answer
262 views

Looking for an algorithm to find a shortest path in a special graph

I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special ...
1
vote
2answers
924 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
65 views

Shortest past including an edge from a given set

I am working on the following problem. There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find ...
1
vote
0answers
51 views

Pathfinding when the graph varies over time

Let's say I want to simulate a very large number of travelers booking flights. For example, a traveler might want to fly from New York to New Delhi. There's no direct flight from New York to New Delhi,...
3
votes
1answer
683 views

Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP): \begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le ...
0
votes
1answer
88 views

Combining Runtime Complexity Expressions with respect to Dijkstra

If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem after running Dijkstra twice (outside the loop), I think I get the following runtime complexity ...
1
vote
0answers
446 views

Edge weight changing during execution in shortest path algorithm

I have an undirected graph with weighted edges, in which I want to find the shortest paths from an initial node to every other node. Obviously Dijkstra's algorithm is usually a good choice, and I have ...
1
vote
0answers
133 views

State-of-the-Art techniques on dynamic shortest path computations

Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target ...
1
vote
1answer
437 views

Bellman-Ford: Find all nodes that have minus infinite distance to source

Given a weighted, directed graph (V, E) may contains some negative cycles and a source node s, I would like to know for all node ...
2
votes
0answers
369 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 ...
4
votes
2answers
1k views

Minimum-weight shortest-path tree

How can we compute the shortest-path tree of minimum total weight for a given connected graph? I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one ...
0
votes
0answers
63 views

Adapting Dijkstra to list all shortest paths [duplicate]

I found a code in the internet for Dijkstra's shortest path algorithm in PHP. The problem is it only shows one possible path. If there are several paths having the same distance, it only outputs one ...
1
vote
1answer
379 views

Running Time of naive implementation of Dijkstra's Algorithm

Here is the "naive" implementation of Dijkstra's algorithm that the professor uses: For a directed graph $G = (V,E)$ as input Initialize: $X = \{s\}$ (the vertices processed so far) ...