Algorithm to find nth shortest path in a weighted graph
Results 1 to 8 of 8

Thread: Algorithm to find nth shortest path in a weighted graph

  1. #1
    Junior Member
    Join Date
    Jul 2003
    Posts
    9

    Algorithm to find nth shortest path in a weighted graph

    Hello,
    I am new to this website. I have recently made a C program, that can graphically simulate the finding of the shortest and 2nd shortest path in a weighted graph. This would be helpful in OSPF routing, where routers can route packets in the 2nd shortest path, if the shortest path has too much traffic. I have formulated the algorithm for finding the nth shortest path in general.To get the source code, visit www.planet-source-code.com.
    Do tell me what you think. Thank you.
    From Abhishek Dwivedi.

  2. #2
    Banned
    Join Date
    Aug 2001
    Location
    Yes
    Posts
    4,429
    Might be a good idea to give the exact URL for the source code... there's quite some code on there

  3. #3
    Leftie Linux Lover the_JinX's Avatar
    Join Date
    Nov 2001
    Location
    Beverwijk Netherlands
    Posts
    2,535
    or post the code here..

    the
    Code:
     CCC   OOO  DDDD  EEEEE
    C   C O   O D   D E
    C     O   O D   D EEE
    C   C O   O D   D E
     CCC   OOO  DDDD  EEEEE
    tag is there for monospaced stuff..
    ASCII stupid question, get a stupid ANSI.
    When in Russia, pet a PETSCII.

    Get your ass over to SLAYRadio the best station for C64 Remixes !

  4. #4
    Junior Member
    Join Date
    Jul 2003
    Posts
    9
    //**************************************
    //
    // Name: Graphic Simulation for Shortest
    // & 2nd shortest path in a Weighted Graph
    // using Dijkstra's Algorithm.
    // Description:This program is used as a
    // simulation for routing packets between r
    // outers. There are 2 subnets, one of whos
    // e weights will have to be entered by the
    // user(positive only).The user will be ask
    // ed for the source and destination nodes,
    // for which he has a choice of 0 to 7 ONLY
    // .(These are the numbers alotted to the n
    // odes). The graphic part will show a gree
    // n colored line drawn from the destinatio
    // n to the source, that indicates the shor
    // test path. This is calculated by Dijkstr
    // a's algorithm. If one more packet is des
    // ired, a second shortest path is chosen t
    // o avoid traffic. This is indicated by th
    // e red colored path. Finally, the user en
    // ters source and dest for subnet 2(0 to 7
    // ONLY).The destination from 1st subnets f
    // orwards the packet to the source of 2nd
    // subnet, and from there by the shortest p
    // ath to the destnation of the 2nd subnet.
    // The code uses a second shortest path alg
    // orithm, which I have devised.
    // By: Abhishek H. Dwivedi
    //
    // Inputs:User must enter the weights of
    // the edges in the first subnet.Then he wi
    // ll be asked to enter the source and dest
    // ination for the 1st subnet(The choices a
    // re from 0 to 7 ONLY as these are the num
    // bers assigned to the nodes).For the seco
    // nd subnet, the weights are predefined, a
    // nd the source and destination entered wi
    // ll be again from 0 to 7 only.
    //
    // Returns:None.Note that the paths are
    // drawn from destination to source in all
    // cases.
    //
    //This code is copyrighted and has// limited warranties.Please see http://
    // www.Planet-Source-Code.com/vb/scripts/Sh
    // owCode.asp?txtCodeId=8733&lngWId=3//for details.//**************************************
    //

    #include<stdio.h>
    #include<conio.h>
    #include<graphics.h>
    #include<dos.h>
    float sum=0,w=0,s,wn,v[8],td=0,e,i,j,n,w1[8],j1[8],arr[8],arr1[8],e1,count,d2,y1;
    float var,a[8][8],d[8],p[8],n1,c,c1,w2;
    void main()


    {
    int gd=DETECT,gm,count1=0;
    clrscr();
    void draw(float,float);
    void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float a1[8][8],float n);
    void ssp();
    void path();
    void initial();
    printf("There are 8 routers in each subnet\n");
    n=8;
    for(i=0;i<n;i++)


    {
    for(j=0;j<n;j++)


    {
    a[i][j]=32767;
    }}
    printf("Enter the weight between 0 & 1 : ");
    scanf("%f",&a[0][1]);
    a[1][0]=a[0][1];
    printf("Enter the weight between 0 & 3 : ");
    scanf("%f",&a[0][3]);
    a[3][0]=a[0][3];
    printf("Enter the weight between 1 & 5 : ");
    scanf("%f",&a[1][5]);
    a[5][1]=a[1][5];
    printf("Enter the weight between 1 & 2 : ");
    scanf("%f",&a[1][2]);
    a[2][1]=a[1][2];
    printf("Enter the weight between 2 & 4 : ");
    scanf("%f",&a[2][4]);
    a[4][2]=a[2][4];
    printf("Enter the weight between 2 & 3 : ");
    scanf("%f",&a[2][3]);
    a[3][2]=a[2][3];
    printf("Enter the weight between 3 & 7 : ");
    scanf("%f",&a[3][7]);
    a[7][3]=a[3][7];
    printf("Enter the weight between 4 & 5 : ");
    scanf("%f",&a[4][5]);
    a[5][4]=a[4][5];
    printf("Enter the weight between 4 & 7 : ");
    scanf("%f",&a[4][7]);
    a[7][4]=a[4][7];
    printf("Enter the weight between 5 & 6 : ");
    scanf("%f",&a[5][6]);
    a[6][5]=a[5][6];
    printf("Enter the weight between 6 & 7 : ");
    scanf("%f",&a[6][7]);
    a[7][6]=a[6][7];
    printf("Enter source and destination node from network 1 ");
    scanf("%f %f",&s,&e);
    clrscr();
    initgraph(&gd,&gm,"c:\\tc\\bgi");
    setcolor(WHITE);
    fillellipse(20,100,7,7);fillellipse(85,50,7,7);
    fillellipse(150,100,7,7);fillellipse(85,150,7,7);
    fillellipse(320,100,7,7);fillellipse(385,50,7,7);
    fillellipse(450,100,7,7);fillellipse(385,150,7,7);
    w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
    w1[5]=385;w1[6]=450;w1[7]=385;
    j1[0]=100;j1[1]=50;j1[2]=100;j1[3]=150;j1[4]=100;j1[5]=50;
    j1[6]=100;j1[7]=150;
    initial();
    setcolor(GREEN);
    for(i=0;i<n;i++)


    {
    v[i]=32767;
    d[i]=32767;
    p[i]=0;
    }
    w=s;
    d[s]=0;
    v[s]=s;
    td=0;
    dijkstra(s,e,v,d,p,a,n);
    path();
    c=w1[e];
    c1=j1[e];
    printf("One more packet ?(Type 1 if yes) ");
    scanf("%f",&count);
    path();
    if(count==1)


    {
    ssp();
    count1=1;
    }
    path();
    w=e;
    setcolor(GREEN);
    count=0;
    printf("Enter source and destination node from network 2 ");
    scanf("%f %f",&s,&e);
    a[0][1]=2;
    a[0][3]=6;
    a[1][2]=2;
    a[1][5]=7;
    a[2][3]=1;
    a[2][4]=2;
    a[4][5]=3;
    a[5][6]=3;
    a[4][7]=2;
    a[6][7]=2;
    a[3][7]=4;
    a[1][0]=2;
    a[3][0]=6;
    a[2][1]=2;
    a[5][1]=7;
    a[3][2]=1;
    a[4][2]=2;
    a[5][4]=3;
    a[6][5]=3;
    a[7][4]=2;
    a[7][6]=2;
    a[7][3]=4;
    setcolor(WHITE);
    fillellipse(20,400,7,7);fillellipse(85,350,7,7);
    fillellipse(150,400,7,7);fillellipse(85,450,7,7);
    fillellipse(320,400,7,7);fillellipse(385,350,7,7);
    fillellipse(450,400,7,7);fillellipse(385,450,7,7);
    w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
    w1[5]=385;w1[6]=450;w1[7]=385;
    j1[0]=400;j1[1]=350;j1[2]=400;j1[3]=450;j1[4]=400;j1[5]=350;
    j1[6]=400;j1[7]=450;
    initial();
    setcolor(GREEN);
    for(i=0;i<n;i++)


    {
    v[i]=32767;
    d[i]=32767;
    p[i]=0;
    }
    w=s;
    d[s]=0;
    v[s]=s;
    td=0;
    line(c,c1,w1[s],j1[s]);
    delay(2000);
    dijkstra(s,e,v,d,p,a,n);
    path();
    count=1;
    if(count1==1)
    ssp();
    path();
    getch();
    }
    void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float a1[8][8],float n)


    {
    while((p1[e])==0)


    {
    for(i=0;i<n;i++)


    {
    if((a1[w][i]+td)<d1[i]&&i!=w&&a1[w][i]!=32767)


    {
    d1[i]=a1[w][i]+td;
    d2=d1[i];
    v1[i]=w;
    }}
    sum=32767;
    for(i=0;i<n;i++)


    {
    if(d1[i]<sum&&i!=s&&p1[i]!=1)


    {
    sum=d1[i];
    wn=i;
    }}
    p1[wn]=1;
    td=d1[wn];
    w=wn;
    }
    }
    void draw(float w,float v1)


    {
    float s,x,y;
    s=(j1[v1]-j1[w])/(w1[v1]-w1[w]);
    if(s<0)
    s=s*-1;
    x=w1[w];
    y=j1[w];
    moveto(x,y);
    if(x==w1[v1])


    {
    while(y!=j1[v1])


    {
    if(y>j1[v1])


    {
    line(x,y,x,y-1);
    delay(10);
    y=y-1;
    }
    else


    {
    line(x,y,x,y+1);
    delay(10);
    y=y+1;
    }}}
    if(y==j1[v1])


    {
    while(x!=w1[v1])


    {
    if(x>w1[v1])


    {
    line(x,y,x-1,y);
    delay(10);
    x=x-1;
    }
    else


    {
    line(x,y,x+1,y);
    delay(10);
    x=x+1;
    }}}
    if(x<w1[v1]&&y<j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x+1,y+s);
    delay(10);
    x=x+1;
    y=y+s;
    }}
    if(x>w1[v1]&&y>j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x-1,y-s);
    delay(10);
    x=x-1;
    y=y-s;
    i=i+1;
    }}
    if(x>w1[v1]&&y<j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x-1,y+s);
    delay(10);
    x=x-1;
    y=y+s;
    i=i+1;
    }}
    if(x<w1[v1]&&y>j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x+1,y-s);
    delay(10);
    x=x+1;
    y=y-s;
    From Abhishek Dwivedi.

  5. #5
    Leftie Linux Lover the_JinX's Avatar
    Join Date
    Nov 2001
    Location
    Beverwijk Netherlands
    Posts
    2,535
    dude, try the [ code ] tag, please !!

    There's an edit button on top of your post..
    ASCII stupid question, get a stupid ANSI.
    When in Russia, pet a PETSCII.

    Get your ass over to SLAYRadio the best station for C64 Remixes !

  6. #6
    Junior Member
    Join Date
    Jul 2003
    Posts
    9
    Hello again,
    I am pasting the source code here as requested by Jinx.
    //**************************************
    //
    // Name: Graphic Simulation for Shortest
    // & 2nd shortest path in a Weighted Graph
    // using Dijkstra's Algorithm.
    // Description:This program is used as a
    // simulation for routing packets between r
    // outers. There are 2 subnets, one of whos
    // e weights will have to be entered by the
    // user(positive only).The user will be ask
    // ed for the source and destination nodes,
    // for which he has a choice of 0 to 7 ONLY
    // .(These are the numbers alotted to the n
    // odes). The graphic part will show a gree
    // n colored line drawn from the destinatio
    // n to the source, that indicates the shor
    // test path. This is calculated by Dijkstr
    // a's algorithm. If one more packet is des
    // ired, a second shortest path is chosen t
    // o avoid traffic. This is indicated by th
    // e red colored path. Finally, the user en
    // ters source and dest for subnet 2(0 to 7
    // ONLY).The destination from 1st subnets f
    // orwards the packet to the source of 2nd
    // subnet, and from there by the shortest p
    // ath to the destnation of the 2nd subnet.
    // The code uses a second shortest path alg
    // orithm, which I have devised.
    // By: Abhishek H. Dwivedi
    //
    // Inputs:User must enter the weights of
    // the edges in the first subnet.Then he wi
    // ll be asked to enter the source and dest
    // ination for the 1st subnet(The choices a
    // re from 0 to 7 ONLY as these are the num
    // bers assigned to the nodes).For the seco
    // nd subnet, the weights are predefined, a
    // nd the source and destination entered wi
    // ll be again from 0 to 7 only.
    //
    // Returns:None.Note that the paths are
    // drawn from destination to source in all
    // cases.
    //
    //This code is copyrighted and has// limited warranties.Please see http://
    // www.Planet-Source-Code.com/vb/scripts/Sh
    // owCode.asp?txtCodeId=8733&lngWId=3//for details.//**************************************
    //

    #include<stdio.h>
    #include<conio.h>
    #include<graphics.h>
    #include<dos.h>
    float sum=0,w=0,s,wn,v[8],td=0,e,i,j,n,w1[8],j1[8],arr[8],arr1[8],e1,count,d2,y1;
    float var,a[8][8],d[8],p[8],n1,c,c1,w2;
    void main()


    {
    int gd=DETECT,gm,count1=0;
    clrscr();
    void draw(float,float);
    void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float a1[8][8],float n);
    void ssp();
    void path();
    void initial();
    printf("There are 8 routers in each subnet\n");
    n=8;
    for(i=0;i<n;i++)


    {
    for(j=0;j<n;j++)


    {
    a[i][j]=32767;
    }}
    printf("Enter the weight between 0 & 1 : ");
    scanf("%f",&a[0][1]);
    a[1][0]=a[0][1];
    printf("Enter the weight between 0 & 3 : ");
    scanf("%f",&a[0][3]);
    a[3][0]=a[0][3];
    printf("Enter the weight between 1 & 5 : ");
    scanf("%f",&a[1][5]);
    a[5][1]=a[1][5];
    printf("Enter the weight between 1 & 2 : ");
    scanf("%f",&a[1][2]);
    a[2][1]=a[1][2];
    printf("Enter the weight between 2 & 4 : ");
    scanf("%f",&a[2][4]);
    a[4][2]=a[2][4];
    printf("Enter the weight between 2 & 3 : ");
    scanf("%f",&a[2][3]);
    a[3][2]=a[2][3];
    printf("Enter the weight between 3 & 7 : ");
    scanf("%f",&a[3][7]);
    a[7][3]=a[3][7];
    printf("Enter the weight between 4 & 5 : ");
    scanf("%f",&a[4][5]);
    a[5][4]=a[4][5];
    printf("Enter the weight between 4 & 7 : ");
    scanf("%f",&a[4][7]);
    a[7][4]=a[4][7];
    printf("Enter the weight between 5 & 6 : ");
    scanf("%f",&a[5][6]);
    a[6][5]=a[5][6];
    printf("Enter the weight between 6 & 7 : ");
    scanf("%f",&a[6][7]);
    a[7][6]=a[6][7];
    printf("Enter source and destination node from network 1 ");
    scanf("%f %f",&s,&e);
    clrscr();
    initgraph(&gd,&gm,"c:\\tc\\bgi");
    setcolor(WHITE);
    fillellipse(20,100,7,7);fillellipse(85,50,7,7);
    fillellipse(150,100,7,7);fillellipse(85,150,7,7);
    fillellipse(320,100,7,7);fillellipse(385,50,7,7);
    fillellipse(450,100,7,7);fillellipse(385,150,7,7);
    w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
    w1[5]=385;w1[6]=450;w1[7]=385;
    j1[0]=100;j1[1]=50;j1[2]=100;j1[3]=150;j1[4]=100;j1[5]=50;
    j1[6]=100;j1[7]=150;
    initial();
    setcolor(GREEN);
    for(i=0;i<n;i++)


    {
    v[i]=32767;
    d[i]=32767;
    p[i]=0;
    }
    w=s;
    d[s]=0;
    v[s]=s;
    td=0;
    dijkstra(s,e,v,d,p,a,n);
    path();
    c=w1[e];
    c1=j1[e];
    printf("One more packet ?(Type 1 if yes) ");
    scanf("%f",&count);
    path();
    if(count==1)


    {
    ssp();
    count1=1;
    }
    path();
    w=e;
    setcolor(GREEN);
    count=0;
    printf("Enter source and destination node from network 2 ");
    scanf("%f %f",&s,&e);
    a[0][1]=2;
    a[0][3]=6;
    a[1][2]=2;
    a[1][5]=7;
    a[2][3]=1;
    a[2][4]=2;
    a[4][5]=3;
    a[5][6]=3;
    a[4][7]=2;
    a[6][7]=2;
    a[3][7]=4;
    a[1][0]=2;
    a[3][0]=6;
    a[2][1]=2;
    a[5][1]=7;
    a[3][2]=1;
    a[4][2]=2;
    a[5][4]=3;
    a[6][5]=3;
    a[7][4]=2;
    a[7][6]=2;
    a[7][3]=4;
    setcolor(WHITE);
    fillellipse(20,400,7,7);fillellipse(85,350,7,7);
    fillellipse(150,400,7,7);fillellipse(85,450,7,7);
    fillellipse(320,400,7,7);fillellipse(385,350,7,7);
    fillellipse(450,400,7,7);fillellipse(385,450,7,7);
    w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
    w1[5]=385;w1[6]=450;w1[7]=385;
    j1[0]=400;j1[1]=350;j1[2]=400;j1[3]=450;j1[4]=400;j1[5]=350;
    j1[6]=400;j1[7]=450;
    initial();
    setcolor(GREEN);
    for(i=0;i<n;i++)


    {
    v[i]=32767;
    d[i]=32767;
    p[i]=0;
    }
    w=s;
    d[s]=0;
    v[s]=s;
    td=0;
    line(c,c1,w1[s],j1[s]);
    delay(2000);
    dijkstra(s,e,v,d,p,a,n);
    path();
    count=1;
    if(count1==1)
    ssp();
    path();
    getch();
    }
    void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float a1[8][8],float n)


    {
    while((p1[e])==0)


    {
    for(i=0;i<n;i++)


    {
    if((a1[w][i]+td)<d1[i]&&i!=w&&a1[w][i]!=32767)


    {
    d1[i]=a1[w][i]+td;
    d2=d1[i];
    v1[i]=w;
    }}
    sum=32767;
    for(i=0;i<n;i++)


    {
    if(d1[i]<sum&&i!=s&&p1[i]!=1)


    {
    sum=d1[i];
    wn=i;
    }}
    p1[wn]=1;
    td=d1[wn];
    w=wn;
    }
    }
    void draw(float w,float v1)


    {
    float s,x,y;
    s=(j1[v1]-j1[w])/(w1[v1]-w1[w]);
    if(s<0)
    s=s*-1;
    x=w1[w];
    y=j1[w];
    moveto(x,y);
    if(x==w1[v1])


    {
    while(y!=j1[v1])


    {
    if(y>j1[v1])


    {
    line(x,y,x,y-1);
    delay(10);
    y=y-1;
    }
    else


    {
    line(x,y,x,y+1);
    delay(10);
    y=y+1;
    }}}
    if(y==j1[v1])


    {
    while(x!=w1[v1])


    {
    if(x>w1[v1])


    {
    line(x,y,x-1,y);
    delay(10);
    x=x-1;
    }
    else


    {
    line(x,y,x+1,y);
    delay(10);
    x=x+1;
    }}}
    if(x<w1[v1]&&y<j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x+1,y+s);
    delay(10);
    x=x+1;
    y=y+s;
    }}
    if(x>w1[v1]&&y>j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x-1,y-s);
    delay(10);
    x=x-1;
    y=y-s;
    i=i+1;
    }}
    if(x>w1[v1]&&y<j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x-1,y+s);
    delay(10);
    x=x-1;
    y=y+s;
    i=i+1;
    }}
    if(x<w1[v1]&&y>j1[v1])


    {
    while(x!=w1[v1])


    {
    line(x,y,x+1,y-s);
    delay(10);
    x=x+1;
    y=y-s;
    i=i+1;
    }
    }}
    void ssp()


    {
    d2=y1=32767;
    setcolor(RED);
    e1=e;
    for(i=0;i<n;i++)


    {
    arr1[i]=v[i];
    arr[i]=v[i];
    }
    while(e1!=s)


    {
    var=a[e1][arr1[e1]]=a[arr1[e1]][e1];
    a[e1][arr1[e1]]=a[arr1[e1]][e1]=32767;
    for(i=0;i<n;i++)


    {
    v[i]=32767;
    d[i]=32767;
    p[i]=0;
    }
    w=s;d[s]=0;
    v[s]=s;
    td=0;
    dijkstra(s,e,v,d,p,a,n);
    if(td<y1)


    {
    y1=td;
    for(i=0;i<n;i++)
    arr[i]=v[i];
    }
    a[e1][arr1[e1]]=a[arr1[e1]][e1]=var;
    e1=arr1[e1];
    }}
    void path()


    {
    while(w!=s)


    {
    if(count==0)


    {
    draw(w,v[w]);
    w=v[w];
    }
    else


    {
    draw(w,arr[w]);
    w=arr[w];
    }}}
    void initial()


    {
    line(w1[0],j1[0],w1[1],j1[1]);
    line(w1[0],j1[0],w1[3],j1[3]);
    line(w1[1],j1[1],w1[5],j1[5]);
    line(w1[1],j1[1],w1[2],j1[2]);
    line(w1[2],j1[2],w1[4],j1[4]);
    line(w1[2],j1[2],w1[3],j1[3]);
    line(w1[3],j1[3],w1[7],j1[7]);
    line(w1[4],j1[4],w1[5],j1[5]);
    line(w1[4],j1[4],w1[7],j1[7]);
    line(w1[5],j1[5],w1[6],j1[6]);
    line(w1[6],j1[6],w1[7],j1[7]);
    }
    From Abhishek Dwivedi.

  7. #7
    AntiOnline n00b
    Join Date
    Feb 2004
    Posts
    665
    Hi,

    Here you go .................. the_JinX ment to put the Code in the [ Code ] tag ............and not to post the Code again .................it's very hard to read the Code like that .

    Code:
     Terms of Agreement:   
    By using this code, you agree to the following terms...   
    1) You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.   
    2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.   
    3) You may link to this code from another website, but ONLY if it is not wrapped in a frame. 
    4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
    
    
    //**************************************
    //     
    // Name: Graphic Simulation for Shortest
    //     & 2nd shortest path in a Weighted Graph 
    //     using Dijkstra's Algorithm.
    // Description:This program is used as a
    //     simulation for routing packets between r
    //     outers. There are 2 subnets, one of whos
    //     e weights will have to be entered by the
    //     user(positive only).The user will be ask
    //     ed for the source and destination nodes,
    //     for which he has a choice of 0 to 7 ONLY
    //     .(These are the numbers alotted to the n
    //     odes). The graphic part will show a gree
    //     n colored line drawn from the destinatio
    //     n to the source, that indicates the shor
    //     test path. This is calculated by Dijkstr
    //     a's algorithm. If one more packet is des
    //     ired, a second shortest path is chosen t
    //     o avoid traffic. This is indicated by th
    //     e red colored path. Finally, the user en
    //     ters source and dest for subnet 2(0 to 7
    //     ONLY).The destination from 1st subnets f
    //     orwards the packet to the source of 2nd 
    //     subnet, and from there by the shortest p
    //     ath to the destnation of the 2nd subnet.
    //     The code uses a second shortest path alg
    //     orithm, which I have devised.
    // By: Abhishek H. Dwivedi
    //
    // Inputs:User must enter the weights of
    //     the edges in the first subnet.Then he wi
    //     ll be asked to enter the source and dest
    //     ination for the 1st subnet(The choices a
    //     re from 0 to 7 ONLY as these are the num
    //     bers assigned to the nodes).For the seco
    //     nd subnet, the weights are predefined, a
    //     nd the source and destination entered wi
    //     ll be again from 0 to 7 only.
    //
    // Returns:None.Note that the paths are 
    //     drawn from destination to source in all 
    //     cases.
    //
    //This code is copyrighted and has// limited warranties.Please see http://
    //     www.Planet-Source-Code.com/vb/scripts/Sh
    //     owCode.asp?txtCodeId=8733&lngWId=3//for details.//**************************************
    //     
    
    #include<stdio.h>
    #include<conio.h>
    #include<graphics.h>
    #include<dos.h>
    float sum=0,w=0,s,wn,v[8],td=0,e,i,j,n,w1[8],j1[8],arr[8],arr1[8],e1,count,d2,y1;
    float var,a[8][8],d[8],p[8],n1,c,c1,w2;
    void main()
    
    
        {
        int gd=DETECT,gm,count1=0;
        clrscr();
        void draw(float,float);
        void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float a1[8][8],float n);
        void ssp();
        void path();
        void initial();
        printf("There are 8 routers in each subnet\n");
        n=8;
        for(i=0;i<n;i++)
    
    
            {
            for(j=0;j<n;j++)
    
    
                {
                a[i][j]=32767;
            }}
    
            printf("Enter the weight between 0 & 1 : ");
            scanf("%f",&a[0][1]);
            a[1][0]=a[0][1];
            printf("Enter the weight between 0 & 3 : ");
            scanf("%f",&a[0][3]);
            a[3][0]=a[0][3];
            printf("Enter the weight between 1 & 5 : ");
            scanf("%f",&a[1][5]);
            a[5][1]=a[1][5];
            printf("Enter the weight between 1 & 2 : ");
            scanf("%f",&a[1][2]);
            a[2][1]=a[1][2];
            printf("Enter the weight between 2 & 4 : ");
            scanf("%f",&a[2][4]);
            a[4][2]=a[2][4];
            printf("Enter the weight between 2 & 3 : ");
            scanf("%f",&a[2][3]);
            a[3][2]=a[2][3];
            printf("Enter the weight between 3 & 7 : ");
            scanf("%f",&a[3][7]);
            a[7][3]=a[3][7];
            printf("Enter the weight between 4 & 5 : ");
            scanf("%f",&a[4][5]);
            a[5][4]=a[4][5];
            printf("Enter the weight between 4 & 7 : ");
            scanf("%f",&a[4][7]);
            a[7][4]=a[4][7];
            printf("Enter the weight between 5 & 6 : ");
            scanf("%f",&a[5][6]);
            a[6][5]=a[5][6];
            printf("Enter the weight between 6 & 7 : ");
            scanf("%f",&a[6][7]);
            a[7][6]=a[6][7];
            printf("Enter source and destination node from network 1 ");
            scanf("%f %f",&s,&e);
            clrscr();
            initgraph(&gd,&gm,"c:\\tc\\bgi");
            setcolor(WHITE);
            fillellipse(20,100,7,7);fillellipse(85,50,7,7);
            fillellipse(150,100,7,7);fillellipse(85,150,7,7);
            fillellipse(320,100,7,7);fillellipse(385,50,7,7);
            fillellipse(450,100,7,7);fillellipse(385,150,7,7);
            w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
            w1[5]=385;w1[6]=450;w1[7]=385;
            j1[0]=100;j1[1]=50;j1[2]=100;j1[3]=150;j1[4]=100;j1[5]=50;
            j1[6]=100;j1[7]=150;
            initial();
            setcolor(GREEN);
            for(i=0;i<n;i++)
    
    
                {
                v[i]=32767;
                d[i]=32767;
                p[i]=0;
            }
    
            w=s;
            d[s]=0;
            v[s]=s;
            td=0;
            dijkstra(s,e,v,d,p,a,n);
            path();
            c=w1[e];
            c1=j1[e];
            printf("One more packet ?(Type 1 if yes) ");
            scanf("%f",&count);
            path();
            if(count==1)
    
    
                {
                ssp();
                count1=1;
            }
    
            path();
            w=e;
            setcolor(GREEN);
            count=0;
            printf("Enter source and destination node from network 2 ");
            scanf("%f %f",&s,&e);
            a[0][1]=2;
            a[0][3]=6;
            a[1][2]=2;
            a[1][5]=7;
            a[2][3]=1;
            a[2][4]=2;
            a[4][5]=3;
            a[5][6]=3;
            a[4][7]=2;
            a[6][7]=2;
            a[3][7]=4;
            a[1][0]=2;
            a[3][0]=6;
            a[2][1]=2;
            a[5][1]=7;
            a[3][2]=1;
            a[4][2]=2;
            a[5][4]=3;
            a[6][5]=3;
            a[7][4]=2;
            a[7][6]=2;
            a[7][3]=4;
            setcolor(WHITE);
            fillellipse(20,400,7,7);fillellipse(85,350,7,7);
            fillellipse(150,400,7,7);fillellipse(85,450,7,7);
            fillellipse(320,400,7,7);fillellipse(385,350,7,7);
            fillellipse(450,400,7,7);fillellipse(385,450,7,7);
            w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
            w1[5]=385;w1[6]=450;w1[7]=385;
            j1[0]=400;j1[1]=350;j1[2]=400;j1[3]=450;j1[4]=400;j1[5]=350;
            j1[6]=400;j1[7]=450;
            initial();
            setcolor(GREEN);
            for(i=0;i<n;i++)
    
    
                {
                v[i]=32767;
                d[i]=32767;
                p[i]=0;
            }
    
            w=s;
            d[s]=0;
            v[s]=s;
            td=0;
            line(c,c1,w1[s],j1[s]);
            delay(2000);
            dijkstra(s,e,v,d,p,a,n);
            path();
            count=1;
            if(count1==1)
            ssp();
            path();
            getch();
        }
    
        void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float a1[8][8],float n)
    
    
            {
            while((p1[e])==0)
    
    
                {
                for(i=0;i<n;i++)
    
    
                    {
                    if((a1[w][i]+td)<d1[i]&&i!=w&&a1[w][i]!=32767)
    
    
                        {
                        d1[i]=a1[w][i]+td;
                        d2=d1[i];
                        v1[i]=w;
                    }}
    
                    sum=32767;
                    for(i=0;i<n;i++)
    
    
                        {
                        if(d1[i]<sum&&i!=s&&p1[i]!=1)
    
    
                            {
                            sum=d1[i];
                            wn=i;
                        }}
    
                        p1[wn]=1;
                        td=d1[wn];
                        w=wn;
                    }
    
                }
    
                void draw(float w,float v1)
    
    
                    {
                    float s,x,y;
                    s=(j1[v1]-j1[w])/(w1[v1]-w1[w]);
                    if(s<0)
                    s=s*-1;
                    x=w1[w];
                    y=j1[w];
                    moveto(x,y);
                    if(x==w1[v1])
    
    
                        {
                        while(y!=j1[v1])
    
    
                            {
                            if(y>j1[v1])
    
    
                                {
                                line(x,y,x,y-1);
                                delay(10);
                                y=y-1;
                            }
    
                            else
    
    
                                {
                                line(x,y,x,y+1);
                                delay(10);
                                y=y+1;
                            }}}
    
                            if(y==j1[v1])
    
    
                                {
                                while(x!=w1[v1])
    
    
                                    {
                                    if(x>w1[v1])
    
    
                                        {
                                        line(x,y,x-1,y);
                                        delay(10);
                                        x=x-1;
                                    }
    
                                    else
    
    
                                        {
                                        line(x,y,x+1,y);
                                        delay(10);
                                        x=x+1;
                                    }}}
    
                                    if(x<w1[v1]&&y<j1[v1])
    
    
                                        {
                                        while(x!=w1[v1])
    
    
                                            {
                                            line(x,y,x+1,y+s);
                                            delay(10);
                                            x=x+1;
                                            y=y+s;
                                        }}
    
                                        if(x>w1[v1]&&y>j1[v1])
    
    
                                            {
                                            while(x!=w1[v1])
    
    
                                                {
                                                line(x,y,x-1,y-s);
                                                delay(10);
                                                x=x-1;
                                                y=y-s;
                                                i=i+1;
                                            }}
    
                                            if(x>w1[v1]&&y<j1[v1])
    
    
                                                {
                                                while(x!=w1[v1])
    
    
                                                    {
                                                    line(x,y,x-1,y+s);
                                                    delay(10);
                                                    x=x-1;
                                                    y=y+s;
                                                    i=i+1;
                                                }}
    
                                                if(x<w1[v1]&&y>j1[v1])
    
    
                                                    {
                                                    while(x!=w1[v1])
    
    
                                                        {
                                                        line(x,y,x+1,y-s);
                                                        delay(10);
                                                        x=x+1;
                                                        y=y-s;
                                                        i=i+1;
                                                    }
    
                                                }}
    
                                                void ssp()
    
    
                                                    {
                                                    d2=y1=32767;
                                                    setcolor(RED);
                                                    e1=e;
                                                    for(i=0;i<n;i++)
    
    
                                                        {
                                                        arr1[i]=v[i];
                                                        arr[i]=v[i];
                                                    }
    
                                                    while(e1!=s)
    
    
                                                        {
                                                        var=a[e1][arr1[e1]]=a[arr1[e1]][e1];
                                                        a[e1][arr1[e1]]=a[arr1[e1]][e1]=32767;
                                                        for(i=0;i<n;i++)
    
    
                                                            {
                                                            v[i]=32767;
                                                            d[i]=32767;
                                                            p[i]=0;
                                                        }
    
                                                        w=s;d[s]=0;
                                                        v[s]=s;
                                                        td=0;
                                                        dijkstra(s,e,v,d,p,a,n);
                                                        if(td<y1)
    
    
                                                            {
                                                            y1=td;
                                                            for(i=0;i<n;i++)
                                                            arr[i]=v[i];
                                                        }
    
                                                        a[e1][arr1[e1]]=a[arr1[e1]][e1]=var;
                                                        e1=arr1[e1];
                                                    }}
    
                                                    void path()
    
    
                                                        {
                                                        while(w!=s)
    
    
                                                            {
                                                            if(count==0)
    
    
                                                                {
                                                                draw(w,v[w]);
                                                                w=v[w];
                                                            }
    
                                                            else
    
    
                                                                {
                                                                draw(w,arr[w]);
                                                                w=arr[w];
                                                            }}}
    
                                                            void initial()
    
    
                                                                {
                                                                line(w1[0],j1[0],w1[1],j1[1]);
                                                                line(w1[0],j1[0],w1[3],j1[3]);
                                                                line(w1[1],j1[1],w1[5],j1[5]);
                                                                line(w1[1],j1[1],w1[2],j1[2]);
                                                                line(w1[2],j1[2],w1[4],j1[4]);
                                                                line(w1[2],j1[2],w1[3],j1[3]);
                                                                line(w1[3],j1[3],w1[7],j1[7]);
                                                                line(w1[4],j1[4],w1[5],j1[5]);
                                                                line(w1[4],j1[4],w1[7],j1[7]);
                                                                line(w1[5],j1[5],w1[6],j1[6]);
                                                                line(w1[6],j1[6],w1[7],j1[7]);
                                                            }
    Source

    Makes it more readable..............

    --Good Luck--

  8. #8
    Junior Member
    Join Date
    Jul 2003
    Posts
    9
    Hello,
    Thank you sword_fish,and Jinx for your suggestions.Here is the algorithm to find the 2nd shortest path.Once you find the shortest path by Dijkstra's algorithm (or Bellman-Ford also),
    make the last edge of the path equal to infinity, thus cutting it off from the graph.Then run the dijkstra's algorithm again.Restore that edge,and make the second edge=infinity,and continue so on for all edges.The shortest path amongst the collection of all those, will be the 2nd shortest path in the graph.
    From Abhishek Dwivedi.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •