Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
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), ...

1
7 8 9 10
11