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
2answers
420 views

Is there a variant of Dijkstra’s algorithm for partial recalculation?

Suppose the following: We use Dijkstra’s algorithm to find the shortest route to our destination. The start node (current vehicle position) keeps changing, i.e. moving towards the destination along ...
2
votes
2answers
511 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 $...
1
vote
0answers
22 views

Why does the inequality $d[v_i] \ge d[v_i−1] + w(v_i−1, v_i)$ hold when all vertices are labelled with their shortest path values upon?

Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \to R$, and let $s \in V$ be a source vertex. Assume that G does not contain a negative cycle reachable from $s$. Then, if we ...
2
votes
0answers
40 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
1answer
2k views

Compute single-source shortest paths in O(n+m) time?

I found the following problem in my textbook and I'm having trouble with coming up with a solution. I'm thinking maybe there's a way to improve Dijkstra's algorithm by using a data structure other ...
0
votes
1answer
36 views

Why does A* fail to find the fastest path when it reaches the goal?

I'm trying to understand how A* works on some simple examples, and something struck me as odd. I could fairly easily come up with situations in which A* "failed". Here is an example: Take a 2x2 grid, ...
3
votes
0answers
158 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 ...
3
votes
2answers
3k views

Bellman-Ford and zero-distance cycle

Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length ...
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
191 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 ...
4
votes
2answers
220 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 ...
3
votes
0answers
42 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
512 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 ...
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 ...
6
votes
2answers
2k views

Finding all vertices on negative cycles

Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a ...
2
votes
1answer
550 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 ...
1
vote
1answer
234 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 ...
0
votes
0answers
227 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
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 ...
5
votes
1answer
2k views

Is the “Bidirectional Dijkstra” algorithm optimal?

In some sites they say the bidirectional Dijkstra's algorithm is optimal, e.g., this, and this. Also there is some software that uses this algorithm (for example this DBMS). But some posts express ...
3
votes
3answers
1k views

Ideal value of d in a d-ary heap for Dijkstra's algorithm

I stumbled upon the following statement: By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time ...
1
vote
1answer
941 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
416 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
529 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
354 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$ ...
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
154 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 ...
2
votes
1answer
979 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 ...
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 $$\...
1
vote
1answer
250 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
387 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-...
-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), ...
-1
votes
1answer
487 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 ...
1
vote
1answer
3k views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
2
votes
1answer
239 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
774 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
756 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
2answers
2k views

How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time. But in this case, we can't track actual shortest path with ...
1
vote
1answer
275 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 ...
1
vote
1answer
582 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 ...
9
votes
1answer
4k views

Dijkstra to favor solution with smallest number of edges if several paths have same weight

You can modify any graph $G$ so that Dijkstra's finds the solution with the minimal number of edges thusly: Multiply every edge weight with a number $a$, then add $1$ to the weight to penalize each ...
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 <...
1
vote
0answers
310 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
191 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
662 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 ...

1
3 4
5
6 7
11