Dijkstra’s Shortest Path Algorithm

  • vertices, or nodes; weighted edges that connect two nodes.
  • In the diagram above, the weight for each edge is written in gray.
  • Distance, an array of distances from the source node ss to each node in the graph, initialized the following way: distance[start] = 0; and for all other nodes v, distdist(v) = ∞(infinity). This is done at the beginning because as the algorithm loops, the distance from the starting node to each node v in the graph will be recalculated and finalized when the shortest distance to finish is found.
  • Q, a queue of all nodes in the graph. At the end of the algorithm’s progress, Q will be empty.
  • S, an empty set, to indicate which nodes the algorithm has visited. At the end of the algorithm, S will contain all the nodes of the graph.

Implementation

  1. While Q is not empty, pop the node v, that is not already in S, from Q with the smallest distance (v). In the first run, the starting node will be chosen because distance was initialized to 0. In the next run, the next node with the smallest distance value is chosen.
  2. Add node v to starting, to indicate that v has been visited.
  3. Update distance values of adjacent nodes of the current node v as follows: for each new adjacent node:
  1. Initialize distances according to the algorithm.

--

--

--

just a junior developer navigating through problems in Rails and React. I like sharing my solutions, thinking processes and sometimes frustration..

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

Recommended from Medium

Salesforce DX and Scratch Organisations: A Quick-Start Guide to Soup Up Your Salesforce…

Johnathan Jones Buys 1972 Oldsmobile 442 For His Dad

React Native vs. Flutter: the key differences every developer should know

Building a Form Handler Service in OpenWhisk

Starting at the Finish Line: How Anzo’s Upcoming Release Will Create a Knowledge Graph with the…

Methods in Ruby

Using Docker to containerize your Node.js

LaTeX or Word?

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
Saman Batool

Saman Batool

just a junior developer navigating through problems in Rails and React. I like sharing my solutions, thinking processes and sometimes frustration..

More from Medium

How To Learn Anything at 50+

d00M$TERS

7- FOLD HAPPINESS

Let us Learn about Hive…..!!