Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Algorithms – Dijkstra’s Algorithm

By Exforsys | on September 17, 2011 |
C Algorithms

This algorithm is a graph search algorithm that solves the shortest path problem for a graph.

In the graph, the path between vertices has a cost or a length, so Dijkstra’s algorithm simply determines the path with the lowest cost between a vertex and another. The algorithm ends when the shortest path from a vertex to a destination vertex was discovered.

How it works:

  • 1) First thing to do is to set the distance value, which is 0 for the current node and infinity for the rest.
  • 2) Set all the nodes as unvisited and initial node as current one;
  • 3) For the current node, calculate the possible distances to the neighbors (if A has distance of 1 and a connecting node B has distance of 4, then the distance from A to B will be 1 + 4 = 5) If this distance is less than the previous recorded one, overwrite it with the newer one. Also, you have to add the unvisited neighbors to the unvisited list;
  • 4) After we have finished checking all the connecting nodes, mark the node as visited. The distance that was recorded is final and minimal;
  • 5) The next current node will be the node with the lowest distance in the unvisited set.
  • 6) If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node, considering all nodes in graph) as the next "current node" and continue from step 3.

Step by step example:

Let us take a peek at a simple example, here is the graph:

As you can see, A is the starting node, the distance to B is 1 and the distance to C is 5, so we co to B:

If you look closely when we were in A, the distance to D was infinite, because at that time we had no path to D from A, but since we are in B, we have a new distance. Also, the best distance to choose now is D because it is the shortest:

And finally, we are left with only one option, the route is direct through E:

Now we have to identify the route. The previous node of E is D, and the previous node of D is B, and B’s previous node is A. So the best route is ABDE. In this case, the total weigh is 4 (1+2+1).

Sample code:

  1.  #include<iostream>
  2.  #include<stdio.h>
  3. using namespace std;
  4. int shortest(int ,int);
  5. int cost[10][10],dist[20],i,j,n,k,m,S[20],v,totcost,path[20],p;
  6.  
  7. int shortest(int v,int n)
  8. {
  9. 	int min;
  10. 	for(i=1;i<=n;i++)
  11. 	{
  12. 		S[i]=0;
  13. 		dist[i]=cost[v][i];
  14. 	}
  15. 	path[++p]=v;
  16. 	S[v]=1;
  17. 	dist[v]=0;
  18. 	for(i=2;i<=n-1;i++)
  19. 	{
  20. 		k=-1;
  21. 		min=31999;
  22. 		for(j=1;j<=n;j++)
  23. 		{
  24. 			if(dist[j]<min && S[j]!=1)
  25. 			{
  26. 				min=dist[j];
  27. 				k=j;
  28. 			} 
  29. 		}
  30. 		if(cost[v][k]<=dist[k])
  31. 			p=1;
  32. 		path[++p]=k;
  33. 		for(j=1;j<=p;j++)
  34. 			cout<<path[j];
  35. 		cout <<"n";
  36. 		//cout <<k;
  37. 		S[k]=1;
  38. 		for(j=1;j<=n;j++)
  39. 			if(cost[k][j]!=31999 && dist[j]>=dist[k]+cost[k][j] && S[j]!=1)
  40. 				dist[j]=dist[k]+cost[k][j];
  41. 	}
  42. 	return v;
  43. }
  44.  
  45. int main()
  46. {
  47. 	int c;
  48. 	cout << "Enter number of vertices = ";
  49. 	cin >> n;
  50. 	cout << "Enter number of edges = "; 
  51. 	cin >>m;
  52. 	cout <<"nEnternEDGE Costn";
  53.  
  54. 	for(k=1;k<=m;k++)
  55. 	{
  56. 		cin >> i >> j >>c;
  57. 		cost[i][j]=c;
  58. 	}
  59.  
  60. 	for(i=1;i<=n;i++)
  61. 		for(j=1;j<=n;j++)
  62. 			if(cost[i][j]==0)
  63. 				cost[i][j]=31999;
  64. 	cout <<"enter initial vertex";
  65. 	cin >>v;
  66. 	cout << v<<"n";
  67. 	shortest(v,n);
  68. 	return 0;
  69. }

Output:

Code explanation:

Just like in the example that I explained earlier, at first it sets the distance of 0 for the current node, next the path to the connecting nodes is checked. The minimal distance will be retained in the min variable, of course after it is checked to be the absolute minimal distance at that point. Also, the cost is compare to the previous value that may exist, and if it is smaller, it will replace the old value. This procedure repeats until there are no more nodes to check.

A visual representation of the graph:

How to insert the values: at first input the number of vertices which is 4 for the above graph and 4 is the name of edges. Then, input the edge and the cost like 1 2 5, which means the cost from 1 to 2 is 5, then 1 3 1 which means the cost from 1 to 3 is 1 and so on. In the end, you will have to input the starting point, which could be 1 like in the above example.

Complexity:

The worst-case running time for the Dijkstra algorithm on a graph with n nodes and m edges is O(n^2) because it allows for directed cycles. It even finds the shortest paths from a source node to all other nodes in the graph. This is basically O(n^2) for node selection and O(m) for distance updates. While O(n^2) is the best possible complexity for dense graphs, the complexity can be improved significantly for sparse graphs.

Applications:

  • Telephone Network – In a telephone network the lines have bandwidth, BW. We want to route the phone call via the highest BW.
  • OSPF (open shortest path first) is a well known real-world implementation of Dijkstra’s algorithm used in internet routing.
  • A related problem is the traveling salesman problem, which is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start.
  • « « C Algorithms – Breadth-First Search (BFS)
    Why You Need Influence Skills ? » »

Author Description

Avatar

Editorial Team at Exforsys is a team of IT Consulting and Training team led by Chandra Vennapoosa.

Free Training

RSSSubscribe 394 Followers
  • Popular
  • Recent
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Insertion Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Selection Sort

    September 11, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Heap Sort

    September 11, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Bubble Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Algorithms – Breadth-First Search (BFS)
  • C Algorithms – Depth-First Search (DFS)
  • C Algorithms – Topological Sort
  • C Algorithms – Graph Theory
  • C Algorithms – Gnome Sort

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT