Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
2
votes
0answers
23 views
Multicommodity shortest path problem on a directed acyclic graph
I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
1
vote
1answer
39 views
For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?
Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of ...
-1
votes
1answer
61 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
0answers
23 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 ...
1
vote
2answers
183 views
Shortest path with odd weight
Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.
We are looking for an algorithm for finding the weight of the shortest odd ...
2
votes
1answer
204 views
Finding the path of a negative weight cycle using Bellman-Ford
I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, ...
2
votes
1answer
176 views
Shortest paths candidate
Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. ...
2
votes
1answer
105 views
Shortest path with exactly $k$ edges
From Skiena's book:
Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ and $k \leq |V|$ be an integer. Design an algorithm ...
1
vote
1answer
67 views
Bellman-Ford parent pointer (?) negative cycle
First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof ...
5
votes
1answer
96 views
Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves
This problem is about finding a route on a square grid.
The starting point is $(1,1)$ and the target point $(n,m)$.
I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$.
...
2
votes
3answers
50 views
Solving system of linear inequalities
I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $
I know these inequalities can be solved using Bellman-Ford algorithm. ...
5
votes
2answers
166 views
Finding shortest and longest paths between two vertices in a DAG
Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are ...
-2
votes
1answer
63 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.
...
5
votes
1answer
144 views
All paths of less than a given length in a directed graph between couple of nodes
Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, ...
3
votes
3answers
197 views
Find a vertex that is equidistant to a set of vertices?
I need help with the following problem:
Input: An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.
Question:
Find a vertex $v$ of $V$ such that the distance ...
2
votes
1answer
77 views
Destination-based vs source-based routing
I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With ...
4
votes
1answer
70 views
What is the maximum number of shortest paths between any pair of vertices in a chordal graph?
A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
0
votes
2answers
85 views
Dijkstra algorithm
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 ...
0
votes
1answer
251 views
Is Dijkstra's algorithm just BFS with a priority queue?
According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
3
votes
2answers
87 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
59 views
Path on an edge-colored DAG using exactly $k$ colors
I have the following problem:
Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$,
does there exist a path from $s$ to $t$ using exactly $k$ ...
1
vote
1answer
122 views
What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?
Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.
What is the asymptotic complexity to calculate the shortest path from $u$ to ...
-1
votes
3answers
98 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?
4
votes
2answers
146 views
Why not relax only edges in Q in Dijkstra's algorithm?
Can someone tell me why almost in every book/website/paper authors use the following:
foreach vertex v in Adjacent(u)
relax(u,v)
when relaxing the edges, ...
-2
votes
3answers
117 views
Defining an “arbitrarily large graph” [closed]
Assume that we want to talk about arbitrarily large graphs, which are however finite. Let $G=(V,E)$ be such a graph.
What restrictions can we impose on the graph and still be in the spirit of the ...
4
votes
3answers
418 views
Dijkstra's algorithm for undirected graphs with negative edges
INPUT: "an undirected, weighted graph (negative weights allowed)"
Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work?
As far as i ...
8
votes
2answers
271 views
What is the fastest algorithm for finding all shortest paths in a sparse graph?
In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall ...
2
votes
1answer
62 views
Bellman-Ford: shortest path
my assumption:
- we have an undirected graph with only positive edges
- the edges are sorted alphabetically:
e.g A-B, A-C, B-D
and e.g not C-A, D-B, ...
8
votes
3answers
384 views
Retrieving the shortest path of a dynamic graph
I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
4
votes
1answer
883 views
Getting negative cycle using Bellman Ford
I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name ...
4
votes
2answers
185 views
Bellman-Ford algorithm - Why can edges be updated out of order?
The Bellman-Ford algorithm determines the shortest path from a source $s$ to all other vertices. Initially the distance between $s$ and all other vertices is set to $\infty$. Then the shortest path ...
4
votes
2answers
470 views
Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$
Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...
6
votes
2answers
581 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 ...
6
votes
1answer
368 views
Formalization of the shortest path algorithm to a linear program
I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem:
For a graph $G=(E,V)$, we defined $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid ...
-2
votes
1answer
173 views
Dijskstra's algorithm, maximum flow
For directed graph $(G=(V, E),s,t,{Ce})$ in which we want to maximize max flow. All edge capacities are at least one. Define the capacity of an $s \to t$ path to be the smallest capacities of ...
0
votes
0answers
130 views
All pairs shortest path, with only a few “required” nodes [closed]
Given a connected graph where I need to visit a subset of nodes. How do I compute the shortest path?
As an example, refer to above image. I need to start from 0 and visit some/all nodes then go ...
3
votes
0answers
85 views
What is the complexity of Hoffman and Pavley's Nth best path algorithm?
I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
3
votes
1answer
355 views
Finding paths with smallest maximum edge weight
I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge.
In the above graph, the easiest path from 1 to 2 is:
...
2
votes
2answers
870 views
Why can't DFS be used to find shortest paths in unweighted graphs?
I understand that using DFS "as is" will not find a shortest path in an unweighted graph.
But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
6
votes
1answer
271 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 ...
3
votes
1answer
410 views
Finding the Shortest path in undirected weighted graph
Is there an algorithm for finding the shortest path in an undirected weighted graph?
0
votes
0answers
49 views
Benchmarking shortest route algorithms [closed]
I am writing a piece for college on shortest route algorithms for data networks.
I would like to compare a selection of A*, Bellman-Ford, Floyd-Warshall, Euclidian shortest path and Dijkstra.
The ...
4
votes
4answers
2k views
Using Dijkstra's algorithm with negative edges?
Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance ...
6
votes
1answer
230 views
Bellman-Ford variation
I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax.
...
4
votes
1answer
122 views
Modified Djikstra's algorithm
So, I'm trying to conceptualize something:
Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats:
movements on ...
10
votes
2answers
1k views
Shortest Path on an Undirected Graph?
So I thought this (though somewhat basic) question belonged here:
Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
1
vote
1answer
254 views
How to construct the found path in bidirectional search
I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables ...
11
votes
1answer
204 views
How many shortest distances change when adding an edge to a graph?
Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
6
votes
3answers
123 views
Unique path in a directed graph
I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've ...
