Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
596 views

Routing algorithm for train network

I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges ...
-3
votes
1answer
1k views

Best heuristic for A*? [closed]

I'm trying to build a maze solver using A* algorithm. The maze is a grid with movement allowed in 4 directions (up, down, left, right). If there's a starting cell (x1, y1) and a destination (x2, y2), ...
0
votes
3answers
433 views

Questions on shortest path and minimum spanning tree

T/F Questions Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Solution - False I think this should be True, as Dijkstra's Algorithm ...
-1
votes
1answer
411 views

Finding multiple shortest path trees from an undirected, weight graph

In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree. How do I find an ...
0
votes
1answer
231 views

How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
2
votes
1answer
193 views

Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph

Is there any efficient algorithm to find shortest distance between all pairs of vertices? The graph is: Cyclic Sparse (each vertex has either 2 or 3 edge) undirected(bidirectional) weighted non-...
2
votes
1answer
628 views

Single pair shortest path algorithm with time a constraint

I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional ...
4
votes
0answers
655 views

A good heuristic for 2D Rubik's cube

I am looking for a good heuristic function for solving a 2D $n\times n$ Rubik's cube using A* search. There is a game already in the play store. The rules of the game: Swiping LEFT means the ...
0
votes
0answers
52 views

Finding the shortest path in non-complete node-weighted graph

Normally, Simulated Annealing (SA) is used in TSP problem to find the near-to-optimal solution, and the graph structure in TSP is a complete graph. Therefore, I want to know whether or not I can use ...
1
vote
1answer
164 views

Find minimum time path between two nodes

I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers. A graph with Vertices representing charges and Edges representing distances ...
4
votes
2answers
198 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
190 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
442 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
193 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
251 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
45 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
178 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
530 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
749 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
95 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
247 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
155 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
243 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
706 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
297 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
139 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
91 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
154 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
181 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
32 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
226 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
787 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
929 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
360 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
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 ...
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
258 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
86 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
484 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
101 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
181 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
3k 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
276 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
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
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 ...