Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
136 views

How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?

For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but ...
5
votes
2answers
1k views

Algorithm: Shortest path (walk) with keys and doors

I'm trying to solve the following algorithm question: A maze is given by a graph (with let's say $v$ vertices and $e$ edges), where $k$ vertices are different keys and, $k$ vertices are the ...
0
votes
0answers
166 views

Shortest path on a dynamic multigraph

I wish I knew the correct terminology for the question that I would like to ask, but I don't, so please forgive me if I am not calling the right things by the right names. The practical problem that I ...
0
votes
1answer
222 views

shortest cycle passing through vertices a and b with changeable edge weights

given a weighted undirected graph with $N$ vertices $(N \leqslant 500)$ we start from vertex $S$ and wo go to $M$ and then we go to $T$ and then we return to $S$. each edge in graph has weight $a_i$ ...
3
votes
0answers
41 views

Defining preferred paths makes $A^*$ heuristic lose admissibility

In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to ...
0
votes
1answer
464 views

Dijkstra's shortest path algorithm without relaxation

Although I have found a very similar question to what I want to ask here (https://codereview.stackexchange.com/questions/96064/dijkstras-algorithm-without-relaxation), yet I didn't find a satisfactory ...
4
votes
1answer
130 views

Given an oriented graph, return true if paths have a specified length

I'm having trouble solving this exercise about graphs, I hope you can help me: Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an ...
1
vote
0answers
23 views

Shortest curve interpolating points with a constraint on the curvature

I'm looking for a method for determining a path for a UAV that interpolates a set of input locations, with a constraint on maximum curvature and given an initial velocity vector. The cost (length) of ...
1
vote
1answer
388 views

Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
2
votes
1answer
488 views

Avoiding loops in Bellman-Ford algorithm

If you apply standard Bellman-Ford algorithm to a graph containing negative loop it can only report its existence. Are there approaches to modify it to find shortest path containing any vertex not ...
0
votes
0answers
204 views

Applicability of Dijkstra's algorithm to hypergraphs

When I search for Dijkstra's algorithm and hypergraphs, I don't get any results discussing it. The Wikipedia page regarding Dijkstra's algorithm doesn't mention hypergraphs and the one regarding ...
1
vote
1answer
341 views

weight constrained shortest path problem variants

Given a graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:E\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ ...
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
1answer
745 views

Hamiltonian path and minimum spanning tree

Suppose i have a graph and i want to find minimum-spanning-tree. As in imperative languages we have to take specific steps from everynode(example ,we use kruskal's algorithm or prim's algorithm) to ...
2
votes
1answer
375 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 ...
3
votes
2answers
1k views

The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm

In the Floyd-Warshall algorithm we have: Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to $j$ for which all intermediate vertices are in the set $\{1, 2, \cdots, k\}$ then \...
2
votes
1answer
481 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-...
0
votes
1answer
41 views

How to prove that a custom iterative algorithm will determine all shortest paths to a graph node?

I'm not sure what the following algorithm does but it seems that it calculates the shortest paths from a node $t$. Initially we're given a graph $G=(V,E)$ with non-negative weights $c(e) \ge0$ for ...
1
vote
1answer
307 views

How to find the minimal path cost from left edge of a grid to the right edge using dynamic programming?

I need to find the minimal path cost from left edge of a $n\times n$ grid to the right edge where each node has some non-negative weight $cost(i,j)$. $i$ represents horizontal coordinates while $j$ ...
7
votes
4answers
2k views

Check if there is only one simple path in graph between nodes x and y`

Let's say we have given simple undirected graph $G$ having $N$ nodes and $M$ bidirectional edges. For given $x$ and $y$ we want to check if in the graph there is only one simple path between them. ...
3
votes
2answers
1k views

Does the A* algorithm visit every node?

I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, ...
0
votes
0answers
153 views

What would Dijkstra's shortest path algorithm complexity be with the following data structure?

Considering $n$ number of pieces of data, what would Dijkstra's shortest path algorithm time complexity be if it was stored using a data structure with following properties? • delete the record ...
0
votes
0answers
61 views

What is the most efficent single-source shorthest path algorithm in unweighted directed grid graph?

As regards the topic. Here is an example of such a graph:
0
votes
1answer
81 views

Dijkstra algorithm step in Introduction to Algorithms

In the introduction to algorithms proof of Dijkstra, I don't understand why the statement "both y and u were in V-S when u was chosen". We add x before y, and so we relax d[y] with the the edge $$\...
5
votes
2answers
851 views

Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

This is from CLRS problem 24.3-5: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$ . Give ...
1
vote
1answer
231 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 ...
2
votes
0answers
368 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-...
1
vote
1answer
702 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
2k 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
4answers
752 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
449 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
266 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
227 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
725 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
719 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
53 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
218 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
211 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
231 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
522 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
215 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
75 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
289 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
49 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
184 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
627 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
836 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
97 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 ...

1 2 3 4 5 10