Dijkstra Positive weight Can I implement like this?

general
, , ,
1

I tried to understand the concept of dijkstra algorithm and tried to write some piece of code to find single source shortest path (Not actual Dijkstra)…I think my logics were okay…My surely I have done something wrong…It’s always giving me a 0 as min distance…What is wrong with my implementation.?
In many implementation I saw they used structure and stuffs I just started Graph algo’s and understand Bfs and Dfs .I just tried to work on dijkstra with those simple ideas.I’ll really appreciate any help. Thanks :slight_smile:

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#define inf 100
using namespace std;
int main()
{
    vector<int> V [100];
    int cost[100][100];
    queue<int> Q;
    int v,e;
    scanf("%d %d",&v,&e);

    for(int a=0;a<e;a++)
    {
        int m,n,z;
        scanf("%d %d %d",&m,&n,&z);
        z=cost[m][n];
        V[m].push_back(n);
    }
    int s,d;
    cout<<"Enter Source:";
    scanf("%d",&s);
    cout<<"Enter Destination:";
    scanf("%d",&d);

    int dis[100]={inf};int color[100]={0};int parent[100];
    dis[s]=0;
    dis[d]=inf+1;
    int source;
    source=s;
    Q.push(s);
    for(int c=0;c<V[d].size();c++)  //I dont need to visit nodes from destination
    {
        color[V[d][c]]=2;
    }                    

    do{


        for(int b=0;b<V[source].size();b++)
        {
            int adj=V[source][b];
            if(color[adj]!=2)
            {
                Q.push(adj);
                color[adj]=1;
            }

            if(dis[adj]>(dis[source]+cost[source][adj]))
            {
                dis[adj]=dis[source]+cost[source][adj]  ;

                parent[adj]=source;
            }
            if(dis[adj]>=dis[d] && adj!=d)  //If I detect any path already crossing limit updated by loop I can ignore it
            {
                color[adj]=2;
            }

        }
        color[source]=2;
        Q.pop();
        source=Q.front();



    }while(!Q.empty());


    cout<<"The minimum distance is "<<dis[d]<<" .\n";

}
2

What are you intending to do with the line z=cost[m][n]; where you are reading input? Is it setting z as the cost of the edge from m to n? Then, the correct way is cost[m][n]=z;

1 Like
3

Yeah,Of corse …How dumb am I?I didn’t see that …
But still it’s not giving me correct answer …Where is the bug…Is something wrong with the logic…?
And thanks to mention that :slight_smile:

4

Hey, don’t! YOU ARE NOT DUMB. Because, if you were, you wouldn’t have come up with this code. And sometimes, blunders bigger than this happens to even the best in the game. So, chill! And let us find out what the problem is :smiley:

1 Like
5

Haven’t checked the complete code again. But this is what i found: int dis[100]={inf}; will also not work the way you intended.

You wanted that the complete array is initialized to inf. But, when you initialize an array like int arr[SIZE] = {val-1, val-2, ..., val-n}; where n < SIZE, then, only the first n values are initialized. All the remaining elements are set to zero. In the above program, dis[0] will be inf and dis[1] to dis[99] will all be 0. The correct way is to use a loop statement and iterate over all the indices and set each of them as inf.

1 Like
6

Also, there is another problem. You need to remove this part from your code

for(int c=0;c<V[d].size();c++)  //I dont need to visit nodes from destination
{
    color[V[d][c]]=2;
}

This is because, if there is an edge from the destination node to another node that is part of the minimum cost path from source node to the destination node, then, that node will not be processed, as we are marking it off as visited.

Instead, what you can do to stop when you reach destination node is, add

if (source == d)
	break;

to the beginning of the do…while loop.

1 Like
7

You can find the code I modified, here. Do take a look, ONLY IF, you are still unable to get your code working, and needs a reference.

All I did is, made the changes as stated before and re-indented the code.

Also, i made the value of inf a very large value (100000000).

8

Yeah I missed that point… By doing this I’m just cancelling some paths…
Thanks a lot ,man…I understood the fact…Yeah and now it’s all good.Thanks again :slight_smile:

1 Like
9

awesome code :slight_smile:

10

@ab19922991 You have misplaced your comment. It should have come at the end of the question.

This entire pgm was coded by @nabil1997, as you can see from the question. All I did was refactor the code for better readability. :smiley:

11

nice exp…

1 Like