You are not logged in. Please login at www.codechef.com to post your questions!

×

Dijkstra Positive weight Can I implement like this?

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 :-)

#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";

}
This question is marked "community wiki".

asked 18 Aug '13, 17:29

nabil1997's gravatar image

3★nabil1997
11111716
accept rate: 0%

edited 18 Aug '13, 22:51

tijoforyou's gravatar image

2★tijoforyou
4.2k52364


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;

link

answered 18 Aug '13, 22:56

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

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 :-)

(19 Aug '13, 09:55) nabil19973★
1

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 :D

(19 Aug '13, 10:04) tijoforyou2★

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.

link

answered 19 Aug '13, 10:09

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

1

nice exp................

(20 Aug '13, 10:41) pandeyarvind704★

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.

link

answered 19 Aug '13, 10:47

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

1

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 :-)

(19 Aug '13, 19:13) nabil19973★

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).

link

answered 19 Aug '13, 10:55

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

awesome code :)

(20 Aug '13, 00:24) ab199229911★

@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. :D

(20 Aug '13, 00:28) tijoforyou2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,914
×1,228
×165
×127

question asked: 18 Aug '13, 17:29

question was seen: 2,385 times

last updated: 20 Aug '13, 10:41