PHPFixing
  • Privacy Policy
  • TOS
  • Ask Question
  • Contact Us
  • Home
  • PHP
  • Programming
  • SQL Injection
  • Web3.0

Tuesday, June 28, 2022

[FIXED] What is difference between BFS and Dijkstra's algorithms when looking for shortest path?

 June 28, 2022     algorithm, breadth-first-search, dijkstra, graph, shortest-path     No comments   

Issue

I was reading about Graph algorithms and I came across these two algorithms:

  • Dijkstra's algorithm
  • Breadth-first search

What is the difference between Dijkstra's algorithm and BFS while looking for the shortest-path between nodes?

I searched a lot about this but didn't get any satisfactory answer!


The rules for BFS for finding shortest-path in a graph are:

  1. We discover all the connected vertices,
  2. Add them in the queue and also
  3. Store the distance (weight/length) from source u to that vertex v.
  4. Update with path from source u to that vertex v with shortest distance and we have it!

This is exactly the same thing we do in Dijkstra's algorithm!


So why are the time complexities of these algorithms so different?

If anyone can explain it with the help of a pseudo code then I will be very grateful!

I know I am missing something! Please help!


Solution

Breadth-first search is just Dijkstra's algorithm with all edge weights equal to 1.

Dijkstra's algorithm is conceptually breadth-first search that respects edge costs.

The process for exploring the graph is structurally the same in both cases.



Answered By - Timothy Shields
Answer Checked By - Marie Seifert (PHPFixing Admin)
  • Share This:  
  •  Facebook
  •  Twitter
  •  Stumble
  •  Digg
Newer Post Older Post Home

0 Comments:

Post a Comment

Note: Only a member of this blog may post a comment.

Total Pageviews

1,206,103

Featured Post

Why Learn PHP Programming

Why Learn PHP Programming A widely-used open source scripting language PHP is one of the most popular programming languages in the world. It...

Subscribe To

Posts
Atom
Posts
Comments
Atom
Comments

Copyright © 2025 PHPFixing