# Questions tagged [shortest-path]

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

526 questions
Filter by
Sorted by
Tagged with
30 views

### Are the following statements True or False? Briefly explain your answer [closed]

a. Best-first search is a special case of Uniform Cost Search. b. A heuristic that always evaluates to h(s)=1 for non-goal search node s is always admissible (given that cost value for each node is ...
247 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)$...
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 ...
118 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 ...
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 ...
71 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 ...
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 ...
87 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

### 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 ...
26 views

### Diameter of a disconnected graph

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

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 ...
86 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 ...
55 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 ...