The tag has no usage guidance.

38 questions
Filter by
Sorted by
Tagged with
1 vote
24 views

### Correctness of bft resulting in shortest path

I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path: source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf The ...
1 vote
34 views

### Proof for Queue in BFS consists of vertices of distance k and k+1

For any vertex v reachable from s, BFS computes a shortest path from s to v (no path from s to v has fewer edges). In order to prove the above proposition, The author of the book has stated that we ...
183 views

### The distinct-vertex $\alpha$-edge variant of the all-pairs shortest paths problem

The following problem is a variant of the all pairs shortest path problem: Given a weighted, directed graph $G=(V,E), |V| = n,|E| = m,$ and an integer $\alpha\ge 1$, how can I find an efficient ...
59 views

### How to find time complexity of Breadth First Search for this tree?

This is what I got from another forum, but honestly doesn't make much sense to me. Time complexity for a single tree doesn't make a lot of sense, since the function in the big O notation might be ...
1 vote
30 views

### Visiting vertices on a graph using DFS and BFS

I have this graph that I created and am wondering how DFS and BFS would work on something like this. I made this graph undirected and am going off the premise that if possible, a vertex should be ...
• 21
56 views

### Shortest path with color constraints

Find shortest path in directed graph (blue and red nodes) that never visits 3 red nodes in a row in $O(V+E)$ time. Not really sure how to approach this.
1 vote
81 views

### Why can't we use BFS with modifications to find shortest paths in weighted graphs

I came across this post about how we can get to all shortest paths from source (u) to destination (v) . If the algorithm is working in O(E + V), why can't we use it (after slight modifications) for ...
220 views

43 views

### How to find more than 1 successive shortest paths between two vertices in unweighted and undirected graph using BFS?

I have tried to find and print more than one successive shortest paths between two vertices in the undirected graph. Using BFS as DFS will not be optimal in this case, as it can go deep into the stack....
• 121
1 vote
84 views

### Why does this BFS solution work for this question about euclidean distance and what's its complexity?

Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector. ...
• 151
93 views

### "Visited" vs "Seen" Positions in Breadth-First Search

I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid. In ...
61 views

### Graphs which favour BFS over DFS and vice versa

I am trying to figure out what kinds of graphs are better suited to BFS and which are better suited to DFS. However i'm struggling to visualise what kind of graphs favour which search. Could someone ...
85 views

### Why MIT lecture breadth-first search algorithm is so complicated?

I watched a video for BFS from MIT and the algorithm the lecturer presented was really complicated compared to what I came up. My solution seems to work fine and walk through the vertices in the ...
• 103