Dijkstra Algorithm

Introduction

Example

Pseudocode

function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0

while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]

Time Complexity

Space Complexity

Disadvantage of Dijkstra

Thank you

Pranjal Bhardwaj
E19CSE432

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

My.props.Hand-Picked => REACT Components & Libraries

Mystery of subscribeOn and observeOn - RxJava 2

SASS & SCSS — Part 1

Implement a Countdown Timer with RxJS in Angular

Do while loop — what are they?

NestJS and Dependency Injection

Should I Learn Elm If I Am a JavaScript Developer?

Ionic 5 and above: SSL Pinning for iOS

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Pranjal Bhardwaj

Pranjal Bhardwaj

More from Medium

Partitions → Interviewbit Arrays Problem

All You Need to Know About “Algorithms Complexity Analysis” and Big O

Liskov Substitution Principle

DAG Algorithm