Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
525
questions
10
votes
1answer
249 views
Shortest Path in a Directed Acyclic Graph with two types of costs
I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$...
2
votes
2answers
23 views
Graph search or shortest path algorithm for graph with multiple “goals”?
I did a project in a class using A* search to solve an 8-puzzle.
But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles.
I’m not sure whether ...
1
vote
1answer
121 views
Bellman Ford Dynamic Programming
I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so ...
1
vote
1answer
44 views
Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS
I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked ...
0
votes
0answers
72 views
Removing any arbitrary vertex from a directed graph?
I came upon this particular question which I do not understand from Jeff E. Algorithms, Chapter 9, ex. 8. https://jeffe.cs.illinois.edu/teaching/algorithms/book/09-apsp.pdf
How can we remove any ...
0
votes
0answers
17 views
Dinamic programming relationships in the all-pairs shortest paths problem
CLRS includes two dynamic programming algorithms for solving the same problem: all-pairs shortest paths.
The kernels of these algorithms (side-by-side) look almost identical, except that they seem to ...
0
votes
1answer
89 views
MIT 6006 Quiz 2: The shortest path task
I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course.
The main idea of creating ...
2
votes
0answers
23 views
Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph
As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
0
votes
1answer
27 views
Diameter of a disconnected graph
Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?
0
votes
2answers
40 views
Online shortest path in ordered DAG
Suppose I have an edge-weighted connected rooted DAG $G = (V, E, r \in V, w \in E \to \mathbb{Z})$ where there exists a sequence of nonempty sets (called "levels") $L_0 = \{r\}, L_1 \subset ...
0
votes
1answer
69 views
Clarification in the proof for the Bellamn-Ford algorithm
While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma:
After k (k >= 0) iterations of relaxations, for any node
u that has at least one path from s (the start ...
0
votes
1answer
29 views
Negative cycle detection using Bellman-Ford and its correctness
I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.
I have 2 doubts about the correctness of the algorithm:
Why are we ...
1
vote
1answer
52 views
Determine whether given f is shortest path function
I have the following question:
Let $G = (V,E)$ be a directed graph with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every ...
0
votes
0answers
34 views
Algorithm to calculate shortest path when updating the heaviest edge in a path [duplicate]
For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge.
$$w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...
2
votes
1answer
101 views
Modified shortest path problem
For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{...
1
vote
0answers
25 views
Is there a Dijkstra like pathfinding with condition satisfication algorithm?
Say we have a place-transition digraph system. A transition can fire if all input places have marks. A transition fires by consuming items from input places and placing one into each output place. A ...
0
votes
1answer
87 views
Create an algorithm for computing the shortest path in O(m + nlogn)
So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non ...
0
votes
1answer
56 views
find shortest paths from source to all vertices using Dijkstra’s Algorithm?
For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ???
For ...
0
votes
0answers
23 views
Bellman-Ford - If an edge was relaxed one more time then there is a cycle in parent pointers
I was given an exercise to prove that the Bellman-Ford algorithm, with maintaining a predecessor array for the vertices, allows finding a negative weight cycle in the graph.
I should emphasize that ...
2
votes
1answer
69 views
Minimum bottleneck path between two vertices in an undirected graph
I have an undirected graph, where the value of the path is the maximum weight among all weights
edges included in it. And I want find the path of minimum value between two given vertices in time $O(n ...
0
votes
0answers
21 views
Is It Of Much Practical Use To Actually Use Fibonacci Heap Over Min Heap In Dijkstra Algorithm?
I know that to get the best technical running time in Dijkstra's shortest path algorithms, using a Fibonacci Heap is the correct way to go. However, the internet and in CLRS state that Fibonacci Heap ...
1
vote
1answer
32 views
Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria
I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week.
For N ...
1
vote
1answer
36 views
How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path
I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, ...
2
votes
1answer
241 views
Gas Station Problem - Dijkstra's Algorithm variation
I am trying to find an algorithm which finds the least expensive route from one town to another.
This is the general setup.
There are a series of one-way roads from some towns to other towns. Not ...
2
votes
0answers
95 views
For which class of graphs can a minimum spanning tree always be associated to a shortest path tree?
Given a connected graph $G=(X,E)$ with positive edge weights. We assume that $G$ contains a unique min weight spanning tree $T_{\min}$ (this is true for example when for all the cuts, the edge with ...
1
vote
0answers
71 views
Johnson's vs Floyd-Warshall for dense graphs
I often read that Floyd-Warshall is a good fit for dense graphs and Johnson's for sparse ones. While it's easy to see why Johnson outperforms Floyd-Warshall on sparse graphs, I'm noticing that ...
1
vote
1answer
68 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
28 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
2answers
41 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
30 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 ...
2
votes
1answer
17 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 ...
3
votes
1answer
61 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 ...
1
vote
0answers
15 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 ...
2
votes
0answers
23 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 ...
0
votes
0answers
28 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 ...
1
vote
1answer
41 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
0answers
39 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
73 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$ (...
0
votes
0answers
21 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,...
4
votes
1answer
232 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 ...
0
votes
0answers
24 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
36 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
88 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
155 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 ...
0
votes
1answer
141 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 (...
0
votes
0answers
65 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
69 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
30 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$, ...
8
votes
1answer
325 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 ...
