TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Discrete Mathematics Dijkstra's Algorithm

Discrete Mathematics Dijkstra's Algorithm with introduction, sets theory, types of sets, set operations, algebra of sets, multisets, induction, relations, functions and algorithms etc.

<< Back to DISCRETE

Dijkstra's Algorithm:

This algorithm maintains a set of vertices whose shortest paths from source is already known. The graph is represented by its cost adjacency matrix, where cost is the weight of the edge. In the cost adjacency matrix of the graph, all the diagonal values are zero. If there is no path from source vertex Vs to any other vertex Vi then it is represented by +∞.In this algorithm, we have assumed all weights are positive.

  1. Initially, there is no vertex in sets.
  2. Include the source vertex Vs in S.Determine all the paths from Vs to all other vertices without going through any other vertex.
  3. Now, include that vertex in S which is nearest to Vs and find the shortest paths to all the vertices through this vertex and update the values.
  4. Repeat the step until n-1 vertices are not included in S if there are n vertices in the graph.

After completion of the process, we got the shortest paths to all the vertices from the source vertex.

Example: Find the shortest paths between K and L in the graph shown in fig using Dijkstra's Algorithm.

Dijkstra's Algorithm

Solution:

Step1: Include the vertex K is S and determine all the direct paths from K to all other vertices without going through any other vertex.

Distance to all other vertices

S K a b c d L
K 0 4(K) ∞ 2(K) ∞ 20(K)

Step2: Include the vertex in S which is nearest to K and determine shortest paths to all vertices through this vertex and update the values. The closest vertex is c.

Distance to all other vertices

S K a b c d L
K 0 3(K, c) 7(K, c) 2(K) 8(K, c) 18(K, c)

Step3: The vertex which is 2nd nearest to K is 9, included in S.

Distance to all other vertices

S K a b c d L
K 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 18(K, c)

Step4: The vertex which is 3rd nearest to K is b, included in S.

Distance to all other vertices

S K a b c d L
K 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 8(K, c, b)

Step5: The vertex which is next nearest to K is d, is included in S.

Distance to all other vertices

S K a b c d L
K(c, a, b, d) 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 8(K, c, b)

Since, n-1 vertices included in S. Hence we have found the shortest distance from K to all other vertices. Thus, the shortest distance between K and L is 8 and the shortest path is K, c, b, L.

Next TopicTravelling Salesman Problem




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf