×

# Dijkstra Positive weight Can I implement like this?

 0 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 #include #include #include #define inf 100 using namespace std; int main() { vector V [100]; int cost[100][100]; queue Q; int v,e; scanf("%d %d",&v,&e); for(int a=0;a(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 "<

 1 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; answered 18 Aug '13, 22:56 4.2k●5●23●64 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) 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)
 1 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. answered 19 Aug '13, 10:09 4.2k●5●23●64 accept rate: 15% 1 nice exp................ (20 Aug '13, 10:41)
 1 Also, there is another problem. You need to remove this part from your code for(int c=0;c
 0 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). answered 19 Aug '13, 10:55 4.2k●5●23●64 accept rate: 15% awesome code :) (20 Aug '13, 00:24) @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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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