New RUET Gate, RUET, Rajshahi

Solved UVA problem (code for bad horse using c/C++ programming)

using namespace std;

class Node{
public:
    string name;
    vector adj;
    bool visited;
    int groupId;

    Node(string str):name(str), visited(false), groupId(-1){}
    int getNeighborCount(){
        return adj.size();
    }
};

class graph{
public:
    unordered_map hashNode;
    vector nodes;

    void createNode(string str){
        Node* n = new Node(str);
        nodes.push_back(n);
        hashNode[str] = n;
    }
};

int main()
{
    freopen("A-small-practice-1.in", "r", stdin);
    freopen("A-small-practice-1.out", "w", stdout);
    int input_count;
    cin>>input_count;
    int counter = 1;
    while(input_count)
    {
        int M;
        cin>>M;
        graph G;
        for(int i=0;i        {
            string str1, str2;
            cin>>str1>>str2;
            g.AddEdge(str1,str2);
        }
        cout<<"Case #"<        input_count--;
    }
    return 0;
}

Solved uva programming problem Jolly Jumper C/C++ code Solution

#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define long long LL
using namespace std;
int num[3010],n;
int diff[3005];
int k;
main()
{
    while(scanf("%d", &n)){
        for(int i=0;i         scanf("%d", &num[i]);
        k=1;
        for(int i =1; i           diff[k++]=abs(num[i]-num[i-1]);

    sort(diff+1,diff+k);
    bool yap=true;
    for(int i=1;i        if(diff[i]!=i){
            yap = false;
            break;
            }
    }
    if(yap) cout<<"Jolly"<    else cout<<"Not jolly"<    }
}

UVA 102 Ecological bin solved problem c/c++

// @BEGIN_OF_SOURCE_CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define long long LL
using namespace std;

int bottles [9 + 3];

int count_movement (int a, int b, int c)
{
    int m = 0;
    for ( int i = 0; i < 9; i++ ) {
        if ( i != a && i != b && i != c )
            m += bottles [i];
    }

    return m;
}

int main ()
{
    while ( scanf ("%d", &bottles [0]) != EOF ) {

        for ( int i = 1; i < 9; i++ )
            scanf ("%d", &bottles [i]);

        char output_str [3 + 3];
        int movements [6];
        int min_movement = INT_MAX;
        char combinations [6] [3 + 2] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};

        // Brown index : 0 3 6
        // Green index : 1 4 7
        // Clear index : 2 5 8

        movements [0] = count_movement (0, 5, 7); // BCG
        movements [1] = count_movement (0, 4, 8); // BGC
        movements [2] = count_movement (2, 3, 7); // CBG
        movements [3] = count_movement (2, 4, 6); // CGB
        movements [4] = count_movement (1, 3, 8); // GBC
        movements [5] = count_movement (1, 5, 6); // GCB

        for ( int i = 0; i < 6; i++ ) {
            if ( movements [i] < min_movement ) {
                min_movement = movements [i];
                strcpy (output_str, combinations [i]);
            }
        }

        printf ("%s %d\n", output_str, min_movement);

    }

    return 0;
}

// @END_OF_SOURCE_CODE

Interrupts

Hardware interrupts were introduced as a way to reduce wasting the processor's valuable time in polling loops, waiting for external events. They may be implemented in hardware as a distinct system with control lines, or they may be integrated into the memory subsystem.
If implemented in hardware, an interrupt controller circuit such as the IBM PC's Programmable Interrupt Controller (PIC) may be connected between the interrupting device and the processor's interrupt pin to multiplex several sources of interrupt onto the one or two CPU lines typically available. If implemented as part of the memory controller, interrupts are mapped into the system's memory address space.
Interrupts can be categorized into these different types:

• Maskable interrupt (IRQ): a hardware interrupt that may be ignored by setting a bit in an interrupt mask register's (IMR) bit-mask.
• Non-maskable interrupt (NMI): a hardware interrupt that lacks an associated bit-mask, so that it can never be ignored. NMIs are used for the highest priority tasks such as timers, especially watchdog timers.
• Inter-processor interrupt (IPI): a special case of interrupt that is generated by one processor to interrupt another processor in a multiprocessor system.
• Software interrupt: an interrupt generated within a processor by executing an instruction. Software interrupts are often used to implement system calls because they result in a subroutine call with a CPU ring level change.
• Spurious interrupt: a hardware interrupt that is unwanted. They are typically generated by system conditions such as electrical interference on an interrupt line or through incorrectly designed hardware.

Processors typically have an internal interrupt mask which allows software to ignore all external hardware interrupts while it is set. Setting or clearing this mask may be faster than accessing an interrupt mask register (IMR) in a PIC or disabling interrupts in the device itself. In some cases, such as the x86 architecture, disabling and enabling interrupts on the processor itself act as a memory barrier; however, it may actually be slower.
An interrupt that leaves the machine in a well-defined state is called a precise interrupt. Such an interrupt has four properties:

• The Program Counter (PC) is saved in a known place.
• All instructions before the one pointed to by the PC have fully executed.
• No instruction beyond the one pointed to by the PC has been executed (that is no prohibition on instruction beyond that in PC, it is just that any changes they make to registers or memory must be undone before the interrupt happens).
• The execution state of the instruction pointed to by the PC is known.

An interrupt that does not meet these requirements is called an imprecise interrupt.
The phenomenon where the overall system performance is severely hindered by excessive amounts of processing time spent handling interrupts is called an interrupt storm.

Microprocessor

micr

Assembly Language Program: Display a character and read two decimal digits and summation of some integer number

.model small
.stack 100h
.data
s1 db 'ENTER TWO NUMBER WHOSE SUM IS LESS THAN 10: $'
S2 DB 0AH,'THE SUM OF $'
S3 DB ' AND $'
S4 DB ' IS $'
A DB ?
B DB ?
C DB ?

.CODE

MAIN PROC

MOV AX,@DATA
MOV DS,AX

MOV AH,9
LEA DX,S1
INT 21H


MOV AH,2
MOV DL,0AH
INT 21H



MOV AH,2
MOV DL,'?'
INT 21H


MOV AH,1
INT 21H
MOV A,AL




MOV AH,1
INT 21H
MOV B,AL


MOV AH,9
LEA DX,S2
INT 21H

MOV AH,2
MOV DL,A
INT 21H

MOV AH,9
LEA DX,S3
INT 21H

MOV AH,2
MOV DL,B

INT 21H


MOV AH,9
LEA DX,S4
INT 21H

SUB A,48D
SUB B,48D
MOV AL,A
ADD AL,B
MOV C,AL

ADD C,48D



MOV AH,2
MOV DL,C

INT 21H

MOV AH,1
INT 21H

MOV AH,4CH
INT 21H

MAIN ENDP
END MAIN

Newton-Raphson Method (C code for finding a real root of an equation)

This article is about Newton's method for finding roots.

In numerical analysis, Newton's method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function.

The Newton-Raphson method in one variable is implemented as follows:
Given a function ƒ defined over the reals x, and its derivative ƒ ', we begin with a first guess x₀ for a root of the function f. Provided the function satisfies all the assumptions made in the derivation of the formula, a better approximation x₁ is

Geometrically, (x₁, 0) is the intersection with the x-axis of a line tangent to f at (x₀, f (x₀)).
The process is repeated as

until a sufficiently accurate value is reached.
This algorithm is first in the class of Householder's methods, succeeded by Halley's method. The method can also be extended to complex functions and to systems of equations.

C code for finding a real root of  the equationf(x)= x*x*x-2*x-5 using Newton-Raphson Method

#include
//#include
#include
int main(){
    //clrscr();
    int i;
    float x,fx,fdx,t;
    printf("Enter x0: ");
    scanf("%f",&x);
    //freopen("file.txt","w",stdout);
    for(;;)
    {
        t=x;
        fx=pow(x,3)-(2*x)-5;
        fdx=3*pow(x,2)-2;
        x=t-(fx/fdx);
        printf("\nthe value of x is::%f\n",x);
        if(fabs(x-t)<=0.0001)
        {
            printf("The root is: %f",x);
            break;
        }
    }
    //fclose(stdout);
    getch();
    return 0;
}

sample output:

Enter x0: 2

the value of x is::2.100000

the value of x is::2.094568

the value of x is::2.094552
The root is: 2.094552

Implementation of Iterative Method

In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method. An iterative method is called convergent if the corresponding sequence converges for given initial approximations. A mathematically rigorous convergence analysis of an iterative method is usually performed; however, heuristic-based iterative methods are also common.
In the problems of finding the root of an equation (or a solution of a system of equations), an iterative method uses an initial guess to generate successive approximations to a solution. In contrast, direct methods attempt to solve the problem by a finite sequence of operations. In the absence of rounding errors, direct methods would deliver an exact solution (like solving a linear system of equations Ax = b by Gaussian elimination). Iterative methods are often the only choice for nonlinear equations. However, iterative methods are often useful even for linear problems involving a large number of variables (sometimes of the order of millions), where direct methods would be prohibitively expensive (and in some cases impossible) even with the best available computing power.

C code to find a real root of the equation 2x=cosx+3 using Iterative method:

  /***********************************************************
* You can use all the programs on  www.engineercse.blogspot.com
* for personal and learning purposes.
* contact azam.ruet10@gmail.com
* To find more C programs, do visit www.engineercse.blogspot.com
* and browse!
*
*                            Coding is poetry!!!
***********************************************************/
#include
#include
#include
#include

int main(){
    int i;
    float f,a,b,x,t;
    scanf("%f",&x);
    //x=(a+b)/2;
    if((sin(x)/2)<1 br="">        for(i=0;i<2000 br="" i="">            t=f;
            //x=0;
            //f=0;
            f=(cos(x)+3)/2;
            printf("%f\n",x);
            //t=f;

            x=f;
            if(fabs(f-t)<=0.0001)
                break;
            //t=f;
        }
        printf("\nThe Root is: %f",x);
    }
    else
        printf("\nThe Method cannot be applied..");

    getch();
}

sample output: 90

90.000000
1.275963
1.645290
1.462788
1.553900
1.508448
1.531154
1.519816
1.525479
1.522651
1.524063
1.523358
1.523710
1.523534

The Root is: 1.523622

Implementing Bisection Method[Numerical Methods]

The method is applicable when we wish to solve the equation f(x) = 0 for the real variable x, where f is a continuous function defined on an interval [a, b] and f(a) and f(b) have opposite signs. In this case a and b are said to bracket a root since, by the intermediate value theorem, the f must have at least one root in the interval (a, b).
At each step the method divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. Unless c is itself a root (which is very unlikely, but possible) there are now two possibilities: either f(a) and f(c) have opposite signs and bracket a root, or f(c) and f(b) have opposite signs and bracket a root. The method selects the subinterval that is a bracket as a new interval to be used in the next step. In this way the interval that contains a zero of f is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.
Explicitly, if f(a) and f(c) are opposite signs, then the method sets c as the new value for b, and if f(b) and f(c) are opposite signs then the method sets c as the new a. (If f(c)=0 then c may be taken as the solution and the process stops.) In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.^[4]

C code implementing bisection method for the equation x*x*x-2*x-5
#include
#include
double f(double x)
{
    return (x*x*x-2*x-5);
}
int main()
{
    double a,b,x;
    scanf("%lf %lf",&a,&b);
    if((f(a)>=0 && f(b)>=0) || (f(a)<0 amp="" b="" br="" f="">    printf("possible\n");
    else
    {
       while(1)
       {
           x=(a+b)/2;
           printf("%lf\n",x);
           if(fabs(f(x)-0)<=0.001)
           {
               printf("%lf\n",x);
               break;
           }
           if((f(a)>=0 && f(x)>=0) || (f(a)<0 amp="" br="" f="" x="">              a=x;
           else
              b=x;
       }
    }
    getch();
    return 0;
}

sample o/p:
2 3
2.500000
2.250000
2.125000
2.062500
2.093750
2.109375
2.101563
2.097656
2.095703
2.094727
2.094238
2.094482
2.094482

Analysis :  

The method is guaranteed to converge to a root of f if f is a continuous function on the interval [a, b] and f(a) and f(b) have opposite signs. The absolute error is halved at each step so the method converges linearly, which is comparatively slow.

Specifically, if c₁ = (a+b)/2 is the midpoint of the initial interval, and c_n is the midpoint of the interval in the nth step, then the difference between c_n and a solution c is bounded by

This formula can be used to determine in advance the number of iterations that the bisection method would need to converge to a root to within a certain tolerance. The number of iterations needed, n, to achieve a given error (or tolerance), ε, is given by:
where
Therefore, the linear convergence is expressed by                     

NQueen problem implementation

 /***********************************************************
* You can use all the programs on  www.engineercse.blogspot.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact azam.ruet10@gmail.com
* To find more C programs, do visit www.engineercse.blogspot.com
* and browse!
*
*                            Coding is poetry!!!
***********************************************************/
#include
#include
#include
void print_solution(int n,int x[]){
      int i,j;
      char c[100][100];
   for(i=1;i<=n;i++){
   for(j=1;j<=n;j++){
          c[i][j]='X';}
        }
   for(i=1;i<=n;i++){
          c[i][x[i]] ='Q';
           }
           for(i=1;i<=n;i++){
           for(j=1;j<=n;j++){
                printf("%c\t",c[i][j]);
                      }
                  printf("\n");
                  }
    }

int place(int x[],int n){

   int i;
   for(i=1;i        if((x[i] == x[n]) || (i-x[i] == n-x[n]) || (i+x[i]==n +x[n])){
       return 0;
         }
           }
    return 1;
       }

void nqueens(int n){
      int x[100],count=0,k=1;

         x[k] = 0;

        while(k != 0){
          x[k] +=1;
          while((x[k] <= n) && ( !place(x,k))){
              x[k] +=1;
                 }
            if(x[k] <= n){
              if(k == n){
                  count++;
                     printf("solution:%d\n",count);
                      print_solution(n,x);
                        }
               else{
                     k++;
                     x[k]=0;
                     }
                }
             else{
                 k--;
                 }

}
}
int main()
{
int n;
printf("enter number of queens\n");
scanf("%d",&n);

nqueens(n);
getch();
return 0;
}

To get more C Program go here
To get more DFS algorithmic code click

Data Structures

Prims Algorithm

Learn C Programming

Implementing BFS(Breath's First Search) using C++

/***********************************************************
* You can use all the programs on  www.engineercse.blogspot.comprogrammers' blog
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact azam.ruet10@gmail.com
* To find more C programs, do visit www.engineercse.blogspot.com
* and browse!
*
*                            Coding is poetry!!!
***********************************************************/

#include
#include
#include
#include
#define inf 1000000
#define clear(x,a) memeset(x,a,sizeof(x))
using namespace std;

bool adj[100][100];
int n, white=1, gray=2, black=3, color[100],d[100],edge, node[100],parent[100],source;
queue Q;
void bfs();

int main()
{
   int start,end;
   cout<<"vertices::";
   cin>>n;
   cout<<"\nedges::";
   for(int i=1;i<=n;i++)
     color[i]=white,d[i]=inf,parent[i]=-1;
     cin>>edge;
     cout<<"\nstart and ending vertex::";
     while(edge--)
     cin>>start>>end,adj[start][end]=true,adj[end][start]=true;
     cout<<"\nsource vertex:";
     cin>>source;
     bfs();
     for(int i=1;i<=n;i++)
     cout<     return 0;
}

void bfs()
{
    d[source]=0;
    Q.push(source);
    color[source]=gray;
    while(!Q.empty())
    {
        int s=Q.front();
        for(int i=0;i<=n;++i)
        {
            if(adj[s][i]and color[i]==white)
            Q.push(i), color[i]=gray, d[i]=d[s]+1, parent[i]=s;
        }
        Q.pop();
    }
}

To get more C Program go here
To get more DFS algorithmic code click

MERGE SORT Algorithm implementation / Application of Divide-and-conquer Method

 /***********************************************************
* You can use all the programs on  www.engineercse.blogspot.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact azam.ruet10.com
* To find more C programs, do visit www.engineercse.blogspot.com
* and browse!
*
*                        Coding is poetry!!!
***********************************************************/
#include
#include
#define MAX_ARY 10
int arr[MAX_ARY];
void merge_sort(int low, int high);
void Merge(int low, int mid, int high);

int main(void)
{

    int j =0;
    printf("\n\nEnter the elements to be sorted:\n");
    for(j=0;j      scanf("%d",&arr[j]);
      printf("\n");
      printf("Before Merging:");
      for(j=0;j      printf("%d ",arr[j]);
    merge_sort(0,MAX_ARY-1);
    printf("After Merging::");
    for(j=0;j    printf("%d  ", arr[j]);

    getch();
}

void merge_sort(int low, int high)
{
    int mid;

    if(low    {
    mid = (low+high)/2;
    merge_sort(low, mid);
    merge_sort(mid+1 , high);
    Merge(low,mid,high);
    }
}

void Merge(int low, int mid, int high){
    int b[MAX_ARY],k;
   int h = low;
   int i = low;
   int j = mid+1;
   while((h<=mid) && (j<=high))
   {
      if(arr[h]<=arr[j]){
         b[i] = arr[h];
         h++;
      }
      else
      {
          b[i] = arr[j];
          j++;
      }
      i++;
   }
      if(h>mid)
      {
         for( k=j;k<=high;k++)
         {
            b[i]=arr[k];
            i++;
         }
      }
      else
      for(k=h; k<=mid;k++)
      {
          b[i] = arr[k];
          i++;
      }
   for(k=low;k<=high;k++)
   arr[k] = b[k];
}

get CSE 402 LAB codes CSE402 LAB practise

Insertion, Deletion & searching operation in BST using Code::Blocks

#include
  #include

  struct treeNode {
        int data;
        struct treeNode *left, *right;
  };

  struct treeNode *root = NULL;

  /* create a new node with the given data */
  struct treeNode* createNode(int data) {
        struct treeNode *newNode;
        newNode = (struct treeNode *) malloc(sizeof (struct treeNode));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return(newNode);
  }

  /* insertion in binary search tree */
  void insertion(struct treeNode **node, int data) {
        if (*node == NULL) {
                *node = createNode(data);
        } else if (data < (*node)->data) {
                insertion(&(*node)->left, data);
        } else if (data > (*node)->data) {
                insertion(&(*node)->right, data);
        }
  }


  /* deletion in binary search tree */
  void deletion(struct treeNode **node, struct treeNode **parent, int data) {
        struct treeNode *tmpNode, *tmpParent;
        if (*node == NULL)
                return;
        if ((*node)->data == data) {
                /* deleting the leaf node */
                if (!(*node)->left && !(*node)->right) {
                        if (parent) {
                                /* delete leaf node */
                                if ((*parent)->left == *node)
                                        (*parent)->left = NULL;
                                else
                                        (*parent)->right = NULL;
                                free(*node);
                        } else {
                                /* delete root node with no children */
                                free(*node);
                        }
                /* deleting node with one child */
                } else if (!(*node)->right && (*node)->left) {
                        /* deleting node with left child alone */
                        tmpNode = *node;
                        (*parent)->right = (*node)->left;
                        free(tmpNode);
                        *node = (*parent)->right;
                } else if ((*node)->right && !(*node)->left) {
                        /* deleting node with right child alone */
                        tmpNode = *node;
                        (*parent)->left = (*node)->right;
                        free(tmpNode);
                        (*node) = (*parent)->left;
                } else if (!(*node)->right->left) {
                        /*
                         * deleting a node whose right child
                         * is the smallest node in the right
                         * subtree for the node to be deleted.
                         */

                        tmpNode = *node;
                        (*node)->right->left = (*node)->left;
                        (*parent)->left = (*node)->right;
                        free(tmpNode);
                        *node = (*parent)->left;
                } else {
                        /*
                         * Deleting a node with two children.
                         * First, find the smallest node in
                         * the right subtree.  Replace the
                         * smallest node with the node to be
                         * deleted. Then, do proper connections
                         * for the children of replaced node.
                         */
                        tmpNode = (*node)->right;
                        while (tmpNode->left) {
                                tmpParent = tmpNode;
                                tmpNode = tmpNode->left;
                        }
                        tmpParent->left = tmpNode->right;
                        tmpNode->left = (*node)->left;
                        tmpNode->right =(*node)->right;
                        free(*node);
                        *node = tmpNode;
                }
        } else if (data < (*node)->data) {
                /* traverse towards left subtree */
                deletion(&(*node)->left, node, data);
        } else if (data > (*node)->data) {
                /* traversing towards right subtree */
                deletion(&(*node)->right, node, data);
        }
  }

  /* search the given element in binary search tree */
  void findElement(struct treeNode *node, int data) {
        if (!node)
                return;
        else if (data < node->data) {
                findElement(node->left, data);
        } else if (data > node->data) {
                findElement(node->right, data);
        } else
                printf("data found: %d\n", node->data);
        return;

  }

  void traverse(struct treeNode *node) {
        if (node != NULL) {
                traverse(node->left);
                printf("%3d", node->data);
                traverse(node->right);
        }
        return;
  }

  int main() {
        int data, ch;
        while (1) {
                printf("1. Insertion in Binary Search Tree\n");
                printf("2. Deletion in Binary Search Tree\n");
                printf("3. Search Element in Binary Search Tree\n");
                printf("4. Inorder traversal\n5. Exit\n");
                printf("Enter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                while (1) {
                                printf("Enter your data:");
                                scanf("%d", &data);
                                insertion(&root, data);
                                printf("Continue Insertion(0/1):");
                                scanf("%d", &ch);
                                if (!ch)
                                        break;
                                }
                                break;
                        case 2:
                                printf("Enter your data:");
                                scanf("%d", &data);
                                deletion(&root, NULL, data);
                                break;
                        case 3:
                                printf("Enter value for data:");
                                scanf("%d", &data);
                                findElement(root, data);
                                break;
                        case 4:
                                printf("Inorder Traversal:\n");
                                traverse(root);
                                printf("\n");
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("u've entered wrong option\n");
                                break;
                }
        }
        return 0;

  }

Program of traversing a binary tree in inorder, preorder and postorder in C++ Programming

#include
#include
#include
struct btree
{
    struct btree *left;
    struct btree *right;
    int no;
};
void postorder(struct btree *trav);
void inorder(struct btree *trav);
void preorder(struct btree *trav);
struct btree * create(struct btree *trav);
main()
{
    struct btree *root=NULL;
    char c;
    clrscr();
    while(1)
    {
        root=create(root);
        cout<<"Do you want to continue : ";
        cin>>c;
        if(c=='n' ||c=='N')
            break;
    }
    cout<"Inoder is    : "

;inorder(root); cout<"Preorder is : ";preorder(root); cout<"Postorder is : ";postorder(root); getch(); } struct btree * create(struct btree *trav) { if(trav==NULL) { trav=new btree; trav->right=NULL; trav->left=NULL; cout<<"Enter the no : "; cin>>trav->no; return(trav); } char choice; cout<<"Enter the left or right child : "; cin>>choice; if(choice == 'r' || choice == 'R') { trav->right=create(trav->right); } if(choice=='l' || choice=='L') { trav->left=create(trav->left); } return(trav); } void inorder(struct btree *trav) { if(trav==NULL) return ; inorder(trav->left); cout<<" "<no; inorder(trav->right); } void preorder(struct btree *trav) { if(trav==NULL) return; cout<<" "<no; preorder(trav->left); preorder(trav->right); } void postorder(struct btree *trav) { if(trav==NULL) return; postorder(trav->left); postorder(trav->right); cout<<" "<no; }

Implementation of Dijkstra's algorithm(Finding shortest path) using C language

C Program to implement Dijkstra's algorithm. Dijkstra's Algorithm finds the shortest path with the lower cost in a Graph. Dijkstra's Algorithm solves the Single Source Shortest Path problem for a Graph. It is a Greedy algorithm and similar to Prim's algorithm. Read more about C Programming Language .

/***********************************************************

* You can use all the programs on  www.engineercse.blogspot.com

* for personal and learning purposes. For permissions to use the

* programs for commercial purposes,

* contact sm.rumi18@gmail.com

* To find more C programs, do visit www.engineercse.blogspot.com

* and browse!

*

*                       Coding is Poetry !!!

***********************************************************/

#include "stdio.h"

#include "conio.h"

#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[])

{

 int i,u,count,w,flag[10],min;

 for(i=1;i<=n;i++)

  flag[i]=0,dist[i]=cost[v][i];

 count=2;

 while(count<=n)

 {

  min=99;

  for(w=1;w<=n;w++)

   if(dist[w]

    min=dist[w],u=w;

  flag[u]=1;

  count++;

  for(w=1;w<=n;w++)

   if((dist[u]+cost[u][w]

    dist[w]=dist[u]+cost[u][w];

 }

}

void main()

{

 int n,v,i,j,cost[10][10],dist[10];

 clrscr();

 printf("\n Enter the number of nodes:");

 scanf("%d",&n);

 printf("\n Enter the cost matrix:\n");

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   scanf("%d",&cost[i][j]);

   if(cost[i][j]==0)

    cost[i][j]=infinity;

  }

 printf("\n Enter the source matrix:");

 scanf("%d",&v);

 dij(n,v,cost,dist);

 printf("\n Shortest path:\n");

 for(i=1;i<=n;i++)

  if(i!=v)

   printf("%d->%d,cost=%d\n",v,i,dist[i]);

 getch();

}

Read more Similar C Programs

Data Structures

Learn C Programming

To get regular updates on new C programs, Algorithm problem solution,