Simple Implementation in Dijkstra algorithm

Question

Hello, Guys I have a little doubt. In this implementation is applied the algorithm of Dijkstra, which returns the paths of lower costs. But it is returning all of the lower cost paths, and I would only need the lower cost path of vertices 0 to 3. Someone would know how to implement this small solution. Obs:(This is a directed graph)

    #include<stdio.h>
    #define QTD 9999
    #define MAX 5

    void dijkstra(int G[MAX][MAX],int n,int inicial);

    int main()
    {
        int i,j,u,l,p;
        int G[MAX][MAX];

        for(l=0 ;l < MAX; l++)
        {
            for( p=0; p< MAX; p++)
            {
                G[l][p] = -1;
            }
        }

        G[0][1]=100;
        G[0][2]=800;
        G[1][3]=500;
        G[1][4]=700;
        G[2][1]=200;
        G[2][3]=500;
        G[4][3]=100;

        for(l=0 ;l < MAX; l++)
        {
            for( p=0; p< MAX; p++)
            {
                printf("%d,",G[l][p]);
            }
            printf("\n");
        }

        printf("\nInforme o node inicial:");
        scanf("%d",&u);
        dijkstra(G,MAX,u);

        return 0;
    }

    void dijkstra(int G[MAX][MAX],int n,int inicial)
    {

        int custo[n][n],distancia[n],pred[n];
        int visitado[n],cont,distanciamin,proxno,i,j;


        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(G[i][j]==-1)
                    custo[i][j]=QTD;
                else
                    custo[i][j]=G[i][j];

        for(i=0;i<n;i++)
        {
            distancia[i]=custo[inicial][i];
            pred[i]=inicial;
            visitado[i]=0;
        }

        distancia[inicial]=0;
        visitado[inicial]=1;
        cont=1;

        while(cont<n-1)
        {
            distanciamin=QTD;


            for(i=0;i<n;i++)
                if(distancia[i]<distanciamin&&!visitado[i])
                {
                    distanciamin=distancia[i];
                    proxno=i;
                }

            //verifica se existe melhor caminho atraves do proximo node
            visitado[proxno]=1;
            for(i=0;i<n;i++){
                if(!visitado[i])
                    if(distanciamin+custo[proxno][i]<distancia[i])
                    {
                        distancia[i]=distanciamin+custo[proxno][i];
                        pred[i]=proxno;
                    }
            }
            cont++;
        }

        //imprime o caminho e a distancia de cada node
        for(i=0;i<n;i++)
            if(i!=inicial)
            {
                printf("\nDistancia do no%d=%d",i,distancia[i]);
                printf("\nCaminho=%d",i);

                j=i;
                do
                {
                    j=pred[j];
                    printf("<-%d",j);
                }while(j!=inicial);
        }
    }

Answer 1

Dijkstra’s algorithm has two important aspects:

• Greedy Algorithm, this way you need to get the most appetizing vertex (with the shortest path).
• Deep Search, this seems to be the problem of your code.

Follow the abstraction of the following logic:

• Compare the adjacent vertices of the initial vertex.
• Choose the Edge with lower weight.
• Follow the edge to change the vertex once at the vertex repeat the previous process.

The graph below is exactly the same as in your program, a detail usually the implementations of the Dijkstra algorithm require beyond an initial vertex a destination vertex, so you can optimize the code and do not need to be doing a blind search. Thus avoiding an infinite loop.

To make Dijkstra’s algorithm work without using the one vertex destination, you will need implement the resources of algorithm A* because it uses auxiliary tables to know which vertices it has already passed, and which path had the lowest cost.