Algorithm (Lab report 06)

Theory: Graph is very important in graphics programming. In mathematics graph has many applications. In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pair wise relations between objects from a certain collection. A "graph" in this context is a collection of "vertices" or "nodes" and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Apparatus:

        i.     Computer.

        ii.    Coding Language.

        iii.   Compiler (Code block, Dev c/c++, Turbo c/c++ etc.)

        iv.   Coding skill.

Algorithm: (Insert a graph)

Step01. Procedure DIJKSTRA SINGLE SOURCE SP(V;E;w; s)

Step02. begin

Step03. VT := fsg;

Step04. for all v 2 (V �� VT ) do

Step05. if (s; v) exists set l[v] := w(s; v);

Step06. else set l[v] := 1;

Step07. while VT 6= V do

Step08. begin

Step09. _nd a vertex u such that l[u] := minfl[v]jv 2 (V �� VT )g;

Step 10. VT := VT [ fug;

Step 11. for all v 2 (V �� VT ) do

Step 12. l[v] := minfl[v]; l[u] + w(u; v)g;

Step 13. endwhile

Step 14. end DIJKSTRA SINGLE SOURCE SP

Source code 01: (Insert a graph)
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<string.h>
#include<math.h>
#define IN 99
#define N 6
int dijkstra(int cost[][N], int source, int target);
int dijsktra(int cost[][N],int source,int target)
{
    int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;
    char path[N];
    for(i=1;i< N;i++)
    {
        dist[i] = IN;
        prev[i] = -1;
    }
    start = source;
    selected[start]=1;
    dist[start] = 0;
    while(selected[target] ==0)
    {
        min = IN;
        m = 0;
        for(i=1;i< N;i++)
        {
            d = dist[start] +cost[start][i];
            if(d< dist[i]&&selected[i]==0)
            {
                dist[i] = d;
                prev[i] = start;

            }
            if(min>dist[i] && selected[i]==0)
            {
                min = dist[i];
                m = i;
            }
        }
        start = m;
        selected[start] = 1;
    }
    start = target;
    j = 0;
    while(start != -1)
    {
        path[j++] = start+65;
        start = prev[start];
    }
    path[j]='\0';
    strrev(path);
    printf("%s", path);
    return dist[target];
}
int main()
{
    int cost[N][N],i,j,w,ch,co;
    int source, target,x,y;
    printf("\tShortest Path Algorithm(DIJKSRTRA's ALGORITHM\n\n");
    for(i=1;i< N;i++)
    for(j=1;j< N;j++)
    cost[i][j] = IN;
    for(x=1;x< N;x++)
    {
        for(y=x+1;y< N;y++)
        {
            printf("Enter the weight of the path between node %d and %d: ",x,y);
            scanf("%d",&w);
            cost [x][y] = cost[y][x] = w;

        }
        printf("\n");
    }
    printf("\nEnter The Source:");
    scanf("%d", &source);
    printf("\nEnter The target");
    scanf("%d", &target);
    co = dijsktra(cost,source,target);
    printf("\nShortest Path: %d\n",co);
    getch();
    return 0;
}

Result:

Sample Input:
Shortest Path Algorithm(DIJKSRTRA's ALGORITHM

Enter the weight of the path between node 1 and 2: 1
Enter the weight of the path between node 1 and 3: 2
Enter the weight of the path between node 1 and 4: 3
Enter the weight of the path between node 1 and 5: 4

Enter the weight of the path between node 2 and 3: 5
Enter the weight of the path between node 2 and 4: 6
Enter the weight of the path between node 2 and 5: 7
Enter the weight of the path between node 3 and 4: 8
Enter the weight of the path between node 3 and 5: 9
Enter the weight of the path between node 4 and 5: 10

Enter the source: 3

Enter the target : 3

Sample output:  
D
Shortest path: 0

Caution: You must change this code. And also change the test value when you print it......Try to make change or modify this.