Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
549
questions
0
votes
0answers
25 views
Single source shortest paths with even path [duplicate]
Given directed graph with non negative weights and vertex s.
I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.
0
votes
0answers
99 views
Shortest path for vehicle routing problem with alternative locations
I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations.
Right now, I'm trying to find ...
0
votes
1answer
49 views
Confused in calculating the shortest-path using Dijkstra's Algorithm [closed]
I am required to find the shortest path using Dijkstra's Algorithm. After performing the calculations, am I getting the following values correct?:
...
0
votes
0answers
320 views
How can an A* algorithm visit all nodes?
Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
0
votes
0answers
70 views
Contraction Hierarchies minimal distance proof
I am trying to implement "Contraction Hierarchies" algorithm and reading the white paper and watching video lectures [6,7]. But still I can't understand proof for the following lemma:
Lemma ...
0
votes
0answers
234 views
Successive shortest path without reduced costs
The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows :
Successive shortest path (for minimum-cost flow) :
while all flow is not ...
0
votes
2answers
1k views
Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal
In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says:
At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable ...
0
votes
0answers
309 views
Finding all edges on any shortest path between two nodes using dijkstra
Given a directed weighted graph, we need to mark all edges (represented by an ordered triple of (source,destination,weight) ) which lie on some shortest path from source to destination (there could be ...
0
votes
2answers
89 views
Finding shortest path between two nodes with a set of forbidden nodes
I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am ...
0
votes
0answers
34 views
Implementation/explanation of the hub based labelling algorithm
I've found plethora of papers describing the performance advantages and basic correctness proofs of the hub-based labelling shortest path algorithm.
However I'd like to implement the algorithm, and ...
0
votes
0answers
54 views
Balancing Steiner trees with Shortest Path trees
I'm working on a problem that combines Steiner Trees and Shortest Path trees. We have a (sparse, connected) graph $G=(V,E)$ with non-negative edge weights and edge lengths, a set of terminals $T \...
0
votes
0answers
196 views
Shortest path between 2 nodes subject to constraints
I am trying to find shortest path between 2 nodes in a graph similar to below:
Each edge has a weight assigned to it. Also, the graph is directional with each edge directing from left to right.
I ...
0
votes
0answers
214 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
293 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$ ...
0
votes
1answer
569 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 ...
0
votes
0answers
252 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 ...
0
votes
0answers
155 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
82 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 $$\...
0
votes
1answer
303 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 ...
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 ...
0
votes
0answers
686 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
...
0
votes
1answer
1k views
given a weighted, directed graph. Give an O(VE)-time algorithm to find, for each vertex vāV, the value Ī“ā(v)=Min uāV{Ī“(u,v)}?
This is the 24.1-5 question in CLRS. I'm having a hard time understanding the questions and also how to solve it. Ī“(u,v) is defined as the shortest path weight from u to v if there exist a path from u ...
0
votes
0answers
78 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 ...
0
votes
0answers
172 views
Trouble implementing back-tracking in RBFS
I'm trying to implement an rbfs search algorithm for the 15 puzzle (pseudo code below).
link to the paper where i found the pseudo code:
https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/viewFile/...
0
votes
0answers
329 views
Shortest path in unweighted graph using an iterator only
I want to find the shortest path (least number of edges) between two nodes in an unweighted graph.
How do I implement this by using a BFSiterator(v) which returns ...
0
votes
0answers
484 views
Fastest Algorithm to find shortest path between two edges in a graph
If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)?
I am trying to answer a question in the EPI book. ...
0
votes
1answer
365 views
Find all shortest paths in a graph where path has even number of edges and greater than 6
Let $G=(V,E)$, a directed with non-negative weights ($w:E\to\mathbb{R}^+$). Describe an algorithm, finds all shortest paths in the graph from a source vertex, $s\in V$, such that, each paths has an ...
0
votes
0answers
918 views
Viterbi algorithm for shortest path calculation
I have to write an essay about shortest path calculation with Viterbi algorithm. Since I am interested in finding the path with the least weight on the network graph, I am a little bit confused how to ...
0
votes
0answers
76 views
How to avoid looping of packets while implementing k-shortest paths algorithm in Network Simulator-3?
I am trying to implement k-shortest paths algorithm in NS-3 for IPv4GlobalRoutingProtocol. I am concerned about how to avoid looping of packets. My implementation calculates k-shortest paths from ...
0
votes
0answers
159 views
A* cost implications of arbitrary/dynamic point on edge in navmesh
I currently have a working implementation of A* using navigation meshes. Agents are moving around a 3d navigation mesh, reaching their target, however often a sub-optimal path is chosen, when ...
0
votes
0answers
640 views
Proof of shortest-paths optimality conditions
I am struggling with understanding the proof of shortest-paths optimality conditions.
Let $G$ be an edge-weighted digraph.
Then values in $distTo[]$ are the shortest path distances from $s$ iff:
For ...
-1
votes
3answers
998 views
Dijkstra algorithm: equal number of shortest paths
If I had a Dijkstra graph with the number shortest paths from Node A to O being 1,
would it be correct to say: the equal number of shortest paths from A to O is 1 and not 0, because that node is ...
-1
votes
1answer
1k views
All Pairs Shortest Path vs Shortest Path [closed]
I do not understand the difference between the All Pairs Shortest Path problem (solved by the FloydāWarshall algorithm) and the Shortest Path problem (solved by Dijkstra's algorithm).
-1
votes
1answer
266 views
WP pseudocode for Dijkstra does not work
I mean Dijkstra's algorithm for the shortest path.
In all descriptions that I saw (including wikipedia),
on every step,
it always selects the nearest neighbor based on examining their weights.
Imagine ...
-1
votes
1answer
132 views
Algortihm for path existence in a N by N board moving with a chess knight
I have a problem which goes like this.
There is an $N$ x $N$ board in which some squares are maked with $x$. The upper left and lower right corner squares are also marked. You have a chess knight ...
-1
votes
1answer
530 views
Is finding negative cycle vertices NP complete?
I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in ...
-1
votes
0answers
47 views
Find an minimum weight elementary path with a given constraint
I have a problem as below and I am really stuck with it as it run with more than the time I desired (about 1 second). I really want your help to build up a more efficient algorithms than mine
Given ...
-1
votes
1answer
532 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
votes
1answer
24 views
What algorithm to apply when a graph have cycles (“circuits”) and some negatives values in order to find the shortest path from $x1$ to all vertices?
What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices? For instance in the following graph?
I know I can'...
-1
votes
1answer
115 views
Minimising two maximum edges in s-t path
I've been trying to solve the following problem:
Problem is the following:
Given a graph and a pair of nodes $s$, $t$ you have to find the path from $s$ to $t$ which minimises the sum of its two ...
-1
votes
3answers
364 views
BFS in K shortest paths
Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes?
If so where can it be useful?
-2
votes
2answers
93 views
Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?
I claim to have solved the travelling salesman problem as follows.
(You will have to be familiar with djikstra's algorithm for this.)
1) I am about to start using djikstra's algorithm on any given ...
-2
votes
1answer
665 views
Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?
NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ...
-2
votes
1answer
434 views
Find the weight of the lightest path from u to v
Find the weight of the lightest path from u to v the goes through node a or/and b.
Do you have a suggestion on how it can be done?
-2
votes
1answer
160 views
why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm
We know Bellman Ford is an algorithm to find the negative cycle.
And here is the algorithm for Bellman Ford
Input: Given a graph G(V,E) and w(e) is weight
Output: Return Yes if negative cycle exists.
...
-2
votes
1answer
1k views
Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification
I provided my answers in the "answer your own question" bit.
I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though?
a)...
-2
votes
1answer
115 views
Shortest path with no two consecutive edges from a certain edge set
Given a graph with nodes $N$ and two sets of edges $E_1$, $E_2$ where no two edges from $E_2$ can be used consecutively, find the shortest path between $n_1, n_2 \in N$.
Is there a smart way to ...
-3
votes
1answer
3k 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), ...
