[Ask] Penjelasan Program Ini Gimana Ya??

[littleshadow]

Permisi om-mastah.. ane mau tanya, maklum masih newbie...

ane punya coding tentang Find Shortest Path menggunakan Dijkstra Algorithm sama Floyd-Warshall Algorithm. yang mau ane tanyain itu penjelasan coding dari keduanya gimana ya??

Dijkstra Algorithm

Code:

#include<stdio.h>
#include<stdlib.h>
void main()
{
    int path[5][5],i,j,min,a[5][5],p,st=1,ed=5,stp,edp,t[5],index;
    printf("enter the cost matrix\n");
    for(i=1;i<=5;i++)
    for(j=1;j<=5;j++)
    scanf("%d",&a[i][j]);
    printf("enter  number of paths\n");
    scanf("%d",&p);
    printf("enter possible paths\n");
    for(i=1;i<=p;i++)
    for(j=1;j<=5;j++)
    scanf("%d",&path[i][j]);
    for(i=1;i<=p;i++)
    {
        t[i]=0;
        stp=st;
        for(j=1;j<=5;j++)
        {
            edp=path[i][j+1];
            t[i]=t[i]+a[stp][edp];
            if(edp==ed)
                break;
            else
                stp=edp;
        }
    }
        min=t[st];index=st;
        for(i=1;i<=p;i++)
    {
        if(min>t[i])
        {
            min=t[i];
            index=i;
        }
    }
printf("minimum cost %d",min);
printf("\n minimum cost path ");
for(i=1;i<=5;i++)
{
    printf("--> %d",path[index][i]);
    if(path[index][i]==ed)
    break;
}
}

Floyd-Warshall Algoritm

Code:

#include <stdio.h>
#include <stdlib.h>

int n; /* Then number of nodes */
int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
            it exists, or 0 if it does not */

void printDist() {
    int i, j;
    printf("    ");
    for (i = 0; i < n; ++i)
        printf("%4c", 'A' + i);
    printf("\n");
    for (i = 0; i < n; ++i) {
        printf("%4c", 'A' + i);
        for (j = 0; j < n; ++j)
            printf("%4d", dist[i][j]);
        printf("\n");
    }
    printf("\n");
}

/*
    floyd_warshall()

    after calling this function dist[i][j] will the the minimum distance
    between i and j if it exists (i.e. if there's a path between i and j)
    or 0, otherwise
*/
void floyd_warshall() {
    int i, j, k;
    for (k = 0; k < n; ++k) {
        printDist();
        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
                /* If i and j are different nodes and if
                    the paths between i and k and between
                    k and j exist, do */
                if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                    /* See if you can't get a shorter path
                        between i and j by interspacing
                        k somewhere along the current
                        path */
                    if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
                        (dist[i][j] == 0))
                        dist[i][j] = dist[i][k] + dist[k][j];
    }
    printDist();
}

int main(int argc, char *argv[]) {
    FILE *fin = fopen("dist.txt", "r");
    fscanf(fin, "%d", &n);
    int i, j;
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            fscanf(fin, "%d", &dist[i][j]);
    fclose(fin);

    floyd_warshall();

    return 0;
}

Thanks Sebelumnya...

[sodri126]

Mungkin aja bawab ane Dewa

[DC™Rebels]

(06-24-2012 11:19 PM)littleshadow Wrote:  Permisi om-om.. ane mau tanya, maklum masih newbie...

ane punya coding tentang Find Shortest Path menggunakan Dijkstra Algorithm sama Floyd-Warshall Algorithm. yang mau ane tanyain itu penjelasan coding dari keduanya gimana ya??

Dijkstra Algorithm

Code:

#include<stdio.h>
#include<stdlib.h>
void main()
{
    int path[5][5],i,j,min,a[5][5],p,st=1,ed=5,stp,edp,t[5],index;
    printf("enter the cost matrix\n");
    for(i=1;i<=5;i++)
    for(j=1;j<=5;j++)
    scanf("%d",&a[i][j]);
    printf("enter  number of paths\n");
    scanf("%d",&p);
    printf("enter possible paths\n");
    for(i=1;i<=p;i++)
    for(j=1;j<=5;j++)
    scanf("%d",&path[i][j]);
    for(i=1;i<=p;i++)
    {
        t[i]=0;
        stp=st;
        for(j=1;j<=5;j++)
        {
            edp=path[i][j+1];
            t[i]=t[i]+a[stp][edp];
            if(edp==ed)
                break;
            else
                stp=edp;
        }
    }
        min=t[st];index=st;
        for(i=1;i<=p;i++)
    {
        if(min>t[i])
        {
            min=t[i];
            index=i;
        }
    }
printf("minimum cost %d",min);
printf("\n minimum cost path ");
for(i=1;i<=5;i++)
{
    printf("--> %d",path[index][i]);
    if(path[index][i]==ed)
    break;
}
}

Floyd-Warshall Algoritm

Code:

#include <stdio.h>
#include <stdlib.h>

int n; /* Then number of nodes */
int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
            it exists, or 0 if it does not */

void printDist() {
    int i, j;
    printf("    ");
    for (i = 0; i < n; ++i)
        printf("%4c", 'A' + i);
    printf("\n");
    for (i = 0; i < n; ++i) {
        printf("%4c", 'A' + i);
        for (j = 0; j < n; ++j)
            printf("%4d", dist[i][j]);
        printf("\n");
    }
    printf("\n");
}

/*
    floyd_warshall()

    after calling this function dist[i][j] will the the minimum distance
    between i and j if it exists (i.e. if there's a path between i and j)
    or 0, otherwise
*/
void floyd_warshall() {
    int i, j, k;
    for (k = 0; k < n; ++k) {
        printDist();
        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
                /* If i and j are different nodes and if
                    the paths between i and k and between
                    k and j exist, do */
                if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                    /* See if you can't get a shorter path
                        between i and j by interspacing
                        k somewhere along the current
                        path */
                    if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
                        (dist[i][j] == 0))
                        dist[i][j] = dist[i][k] + dist[k][j];
    }
    printDist();
}

int main(int argc, char *argv[]) {
    FILE *fin = fopen("dist.txt", "r");
    fscanf(fin, "%d", &n);
    int i, j;
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            fscanf(fin, "%d", &dist[i][j]);
    fclose(fin);

    floyd_warshall();

    return 0;
}

Thanks Sebelumnya...

Nunggu gengsternya aja om karna gengster DC pinter2 om :)

[littleshadow]

aduhh... bantuin donk gan...

[monyett]

Ini perlu dijelasin baris per baris atau gimana? Yang gak paham bahasa C nya atau algoritmanya? Kalo algoritmanya, ada penjelasan di http://en.wikipedia.org/wiki/Floyd%E2%80..._algorithm sama http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Fyi, wikipedia itu ensiklopedi lho, ditulis untuk orang awam.

[guntur9090]

Maksudnya penjelasan outputnya atau penjelasan cara kerjanya omz?

[momoi]

(06-24-2012 11:19 PM)littleshadow Wrote:  Permisi om-om.. ane mau tanya, maklum masih newbie...

ane punya coding tentang Find Shortest Path menggunakan Dijkstra Algorithm sama Floyd-Warshall Algorithm. yang mau ane tanyain itu penjelasan coding dari keduanya gimana ya??

Dijkstra Algorithm

Code:

#include<stdio.h>
#include<stdlib.h>
void main()
{
    int path[5][5],i,j,min,a[5][5],p,st=1,ed=5,stp,edp,t[5],index;
    printf("enter the cost matrix\n");
    for(i=1;i<=5;i++)
    for(j=1;j<=5;j++)
    scanf("%d",&a[i][j]);
    printf("enter  number of paths\n");
    scanf("%d",&p);
    printf("enter possible paths\n");
    for(i=1;i<=p;i++)
    for(j=1;j<=5;j++)
    scanf("%d",&path[i][j]);
    for(i=1;i<=p;i++)
    {
        t[i]=0;
        stp=st;
        for(j=1;j<=5;j++)
        {
            edp=path[i][j+1];
            t[i]=t[i]+a[stp][edp];
            if(edp==ed)
                break;
            else
                stp=edp;
        }
    }
        min=t[st];index=st;
        for(i=1;i<=p;i++)
    {
        if(min>t[i])
        {
            min=t[i];
            index=i;
        }
    }
printf("minimum cost %d",min);
printf("\n minimum cost path ");
for(i=1;i<=5;i++)
{
    printf("--> %d",path[index][i]);
    if(path[index][i]==ed)
    break;
}
}

Floyd-Warshall Algoritm

Code:

#include <stdio.h>
#include <stdlib.h>

int n; /* Then number of nodes */
int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
            it exists, or 0 if it does not */

void printDist() {
    int i, j;
    printf("    ");
    for (i = 0; i < n; ++i)
        printf("%4c", 'A' + i);
    printf("\n");
    for (i = 0; i < n; ++i) {
        printf("%4c", 'A' + i);
        for (j = 0; j < n; ++j)
            printf("%4d", dist[i][j]);
        printf("\n");
    }
    printf("\n");
}

/*
    floyd_warshall()

    after calling this function dist[i][j] will the the minimum distance
    between i and j if it exists (i.e. if there's a path between i and j)
    or 0, otherwise
*/
void floyd_warshall() {
    int i, j, k;
    for (k = 0; k < n; ++k) {
        printDist();
        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
                /* If i and j are different nodes and if
                    the paths between i and k and between
                    k and j exist, do */
                if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                    /* See if you can't get a shorter path
                        between i and j by interspacing
                        k somewhere along the current
                        path */
                    if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
                        (dist[i][j] == 0))
                        dist[i][j] = dist[i][k] + dist[k][j];
    }
    printDist();
}

int main(int argc, char *argv[]) {
    FILE *fin = fopen("dist.txt", "r");
    fscanf(fin, "%d", &n);
    int i, j;
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            fscanf(fin, "%d", &dist[i][j]);
    fclose(fin);

    floyd_warshall();

    return 0;
}

gan knpa ngga make #include <iostream.h>

gunanya:
1.iostream.h
2.conio.h
3.stdio.h


tolong jelasin donk gan...
ane ada UTS minggu depan.... tolong pencerahan nya gan....
binggung knpa ngga dipake iostream.h gan...
mohon bimbingan nya y gan.. makasiii