# Questions tagged [shortest-path]

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

520 questions
Filter by
Sorted by
Tagged with
63 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 ...
23 views

### Difficulty in Understanding the statement of question

Given a weighted, directed graph G with no negative-weight cycles, let m be the maximum over all vertices of the minimum number of edges in a shortest path from the source s to v. (Here, the shortest ...
22 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 ...
24 views

### Diameter of a disconnected graph

Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?
38 views

50 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 ...
24 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 ...
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, ...
466 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 ...
211 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 ...
2k views

### Shortest path in a maze where you can break one wall

How would I solve the following problem? You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s ...
18k 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 ...
986 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 ...
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 ...
65 views

158 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 ...
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: ...
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,...
450 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 ...