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
1answer
51 views

How Do You Design an Algorithm for This Graph

Introduction I'm not really understanding my algorithms class. One of our HW assignments is to design an efficient algorithm for this graph Questions Give an efficient algorithm to find the fastest ...
0
votes
1answer
26 views

What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle?

Typing out negative weight cycle again and again is kind of annoying, so for the rest of the question I'm going to abbreviate it to NWC. I'm writing an optimized version of Bellman-Ford's Shortest ...
0
votes
1answer
274 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 ...
1
vote
1answer
435 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 ...
1
vote
1answer
32 views

A pathfinding algorithm for graphs in which arc weights can change over time

So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction. Here's the situation, I have a weighted undirected ...
0
votes
2answers
35 views

Is There Any Shortest Path Algorithm That Finds The Shortest Path Between Only Two Nodes

The Dikstra shortest path algorithm on a weighted graph, directional or bidirectional, pretty quick. There is also the Bellman Ford algorithm. However, these two find the shortest path between one ...
0
votes
1answer
896 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
1answer
21 views

Shortest path form node X to nodes A, B, C in graph

I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and ...
3
votes
1answer
56 views

Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same

Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all ...
2
votes
1answer
15 views

Raptor algorithm: find next best paths

I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to ...
1
vote
0answers
11 views

Queries on unbounded knapsack

Given $n$ types of items with integer cost $c_{i}$ (there is an unlimited number of items of each type), such that $c_{i} \leq c$ for all $i = 1, 2, \dots, n$, answer (a lot of) queries of form "is ...
1
vote
0answers
16 views

Finding multiple paths through a grid such that every grid square is equally used

Setup Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
2
votes
1answer
4k views

Single Source Shortest Paths using Product Construction

I am trying to solve a bounded SSSP problem as follows: Given a connected weighted graph with non-negative edges (might have cycles), find the shortest path from a vertex s to a vertex t with ...
0
votes
0answers
24 views

Least-weight path in a DAG--why not just use Dijkstra?

I have an assignment to find the least-weight path in a DAG from a source to a target. But the class has already discussed Dijkstra's algorithm, so I'm wondering, why not just use that? It seems too ...
0
votes
0answers
34 views

Routing algorithm for public transport without timetable

I'm trying to implement a simplified version of RAPTOR algorithm for journey planning. Raptor tries to find fastest route based on the arrival and departure time in each stop. There is a concept of a ...
0
votes
0answers
69 views

Shortest tour visiting given set of nodes in knight tour graph

Problem: Given knight tour graph $G$ ($8 \times 8$ nodes) and a set of nodes $\{ v_{1}, v_{2}, \dots, v_{n} \} = V \subset V(G)$, find a minimal length tour in $G$ that visits all nodes from $V$ (...
2
votes
3answers
136 views

Shortest path between any origin to any destination through some way stations

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm? You can visit those way stations ...
7
votes
3answers
2k views

Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop

The Floyd-Warshall algorithm is defined as follows: ...
1
vote
1answer
171 views

Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
0
votes
0answers
20 views

Path for a tube between two points including constraints

I need to create paths for tubes, pipes, and ducts connecting two points in an automated fashion. For example, I want to create a path for a tube between the two red endpoints in this screenshot (yes,...
3
votes
0answers
89 views

How to extend Bellman-Ford to solve the $k$ shortest path routing?

Browsing the wikipedia I got to this page where it is said: Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
2
votes
1answer
337 views

Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|). I was thinking about using Bellman-Ford to solve the ...
0
votes
0answers
22 views

Johnson shortest path work for undirected graphs?

Does Johnson's shortest path algorithm works for Undirected graphs? All examples I am seeing with Johnson algorithm use directed graphs, but nobody is clear about what kind of graph was it designed ...
0
votes
0answers
26 views

Maximum weight path

While preparing for an exam, I stumbled upon a question and I'm not sure if I answered correctly. The question is: In a directed weighted graph G in which each ...
3
votes
2answers
79 views

Shortest path between all pairs with colored nodes

I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly. The question is: Let's say we have a directed graph with no ...
3
votes
2answers
111 views

Why doesn't Dijkstra's use a shortest-path first search?

When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we ...
6
votes
1answer
436 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
7
votes
1answer
272 views

How hard is finding the shortest path in a graph matching a given regular language?

Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
2
votes
1answer
127 views

Dijkstra without decrease key

I was reading though this paper, which suggests using dijkstra without edge relaxation, but to rather to just insert new nodes, cf page 16 for the pseudo code. But to me the code looks wrong. I think ...
0
votes
1answer
134 views

Why is my algorithm version so slow with this input?

Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (...
11
votes
2answers
5k views

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive. the algo depends on finding a new weight function (w') that ...
0
votes
0answers
50 views

Time complexity analysis of shortest path algorithm

Below is Dijkstra's algorithm from CLRS: In the time complexity analysis of Dijkstra, CLRS says, RELAX() contains call to DECREASE-KEY(), which is essentially reducing edge weights associated with ...
0
votes
0answers
39 views

How Dijkstra's algorithm forms shortest path tree when multiple nodes have same shortest path length

I came across following problem: Consider below graph: What will be the shortest path tree starting with node $A$ returned by Dijkstra's algorithm, if we assume priority queue is implemented ...
1
vote
1answer
29 views

Dijkstra shortest path yields unintuitive results

Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, ...
1
vote
1answer
29 views

Dijikstra's algorithm with “hull” value catch

Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here. Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, ...
4
votes
1answer
67 views

Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
9
votes
3answers
6k views

Finding negative cycles for cycle-canceling algorithm

I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is ...
3
votes
1answer
414 views

Shortest paths between given red vertices and arbitrary blue vertices

Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the ...
3
votes
0answers
65 views

Dynamic all pairs shortest path edge removal

I have a planar(|E|=O(V)) undirected graph with positive edge weights. I have already calculated all pairs shortest path with Floyd–Warshall algorithm. Now I want to recalculate APSP with an edge ...
5
votes
1answer
950 views

Dijkstra with max instead of sum

Is it true that if we replace in the Dijkstra algorithm + with max, then the resulting algorithm correctly solves the problem of ...
1
vote
3answers
63 views

What's the best algorithm to find the shortest path between 2 vertices in a graph?

Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?
0
votes
0answers
20 views

Decomposition of graph to subgraphs according to parallel edges

I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges. If N parallel ...
3
votes
1answer
51 views

Maximum value of arbitrage

I'm trying to solve this from The Algorithm Design Manual: 6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time ...
1
vote
1answer
80 views

Determine shortest path in a 4x5 grid graph

Suppose we had a graph $G = (V,E)$. This graph can also be seen as a $4x5$ grid graph as shown in the image. There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and ...
2
votes
1answer
15 views

Performant algorithm to find edges without cross overs

I have a series of graphs with points plotted like this: Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don'...
4
votes
1answer
66 views

Optimal root in shortest path tree (SPT)

I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs. ...
2
votes
2answers
122 views

How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is ...
2
votes
1answer
26 views

Proving inequalities related to Dijkstra's algorithm

Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$. Define $IN(v)$ as the set of in-neighbors of $v$. Define $w(u,v)$ as the weight of the edge $(u,v)$. I am asked to ...
1
vote
0answers
153 views

Remove a vertex from a graph keeping shortest path distance same

How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.
5
votes
2answers
952 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
2 3 4 5
11