Recent

Author Topic: Problem trying to implement Dijkstra algorithm  (Read 6498 times)

FallingStar

  • Newbie
  • Posts: 6
Problem trying to implement Dijkstra algorithm
« on: October 30, 2015, 02:50:11 pm »
My solution: http://ideone.com/Dnh5Zw
Problem link: http://www.spoj.com/problems/SHPATH/
I am trying to implement the Dijkstra algorithm with a binary heap.
My submission always get a NZEC (non-zero exit code).
I would be happy if someone could help me to point out what's wrong in my solution, or ways to optimize it.
I already posted in the SPOJ forum but it didn't help.

Some code explanation (the code is quite long and odd):

Variables:
adj: adjacency list (graph)
last: adj list index (graph)
heap: binary heap
city: city name
visited: True if the city has been visited at least once, False otherwise
i,j,k: loop index variables
des: dest represents a city, cost represents the cost to reach it
heapidx: store the index of the heap array that contains the city, e.g if heap[3].dest = 2 then heapidx[2] = 3.
dist: the cost to reach a city

Procedures:
ReadString: seperate the first word from the second word
Div2: Some special hadling since array index start at 0
Swap: swap 2 element in the heap and update their heapidx
MinHeapify: restore heap properties
Pop: delete first element in heap
Push: push an element (a city) into the heap
Update: update a city's cost (Dijkstra) and maintaining the heap's properties
Findpath: find the shortest path

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: Problem trying to implement Dijkstra algorithm
« Reply #1 on: October 30, 2015, 03:23:19 pm »
Your second  link content is wrong.
The wikipedia write up is much much better and you may learn from it how to implement this. (Juniors don't do Dijkstra).

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm


Oh, and plz let me know if and  when you spot the difference ;)
« Last Edit: October 30, 2015, 03:26:19 pm by Thaddy »
Specialize a type, not a var.

FallingStar

  • Newbie
  • Posts: 6
Re: Problem trying to implement Dijkstra algorithm
« Reply #2 on: October 30, 2015, 04:48:28 pm »
The second link is a link to the problem I'm trying to solve that uses the Dijkstra algorithm, not to the algorithm itself.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Problem trying to implement Dijkstra algorithm
« Reply #3 on: October 30, 2015, 05:07:40 pm »
I would be happy if someone could help me to point out what's wrong in my solution, or ways to optimize it.
I already posted in the SPOJ forum but it didn't help.
Don't think about (premature) optimization yet, your solution doesn't even pass the sample input. That's the first barrier you have to pass before submitting a solution to any online judge problem. You have to learn how to debug, properly, using a real debugger. Here's what happens when your program is fed with the sample input:
Code: [Select]
Program received signal SIGSEGV, Segmentation fault.
0x000000000040042f in UPHEAP (INDX=4294967294) at test.pas:55
55   While (indx <> 0) and (heap[Div2(indx)].cost > heap[indx].cost) do
(gdb) bt
#0  0x000000000040042f in UPHEAP (INDX=4294967294) at test.pas:55
#1  0x00000000004004d7 in PUSH (CITYINDEX=0, COST=5) at test.pas:69
#2  0x00000000004006ac in FINDPATH (CITYINDX=2, DESTINATION=...) at test.pas:97
#3  0x0000000000400c62 in main () at test.pas:138
Got any clue already?

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: Problem trying to implement Dijkstra algorithm
« Reply #4 on: October 30, 2015, 05:24:00 pm »
The second link is a link to the problem I'm trying to solve that uses the Dijkstra algorithm, not to the algorithm itself.
You obviously haven't the patience to read up and until the solution and rely on a false, wrong and ill-informed source of information.
You are given a wrong start in the first place. READ IT!! or I'll come over to your house. (In a matter of speak. I am not very dangerous).
Specialize a type, not a var.

FallingStar

  • Newbie
  • Posts: 6
Re: Problem trying to implement Dijkstra algorithm
« Reply #5 on: October 30, 2015, 11:51:48 pm »
your solution doesn't even pass the sample input.
What sample input? In ideone I already fed my solution with the sample input and it succeed.

Thaddy:
Don't you understand the difference between theory and exercise?
« Last Edit: October 31, 2015, 12:04:21 am by FallingStar »

Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Problem trying to implement Dijkstra algorithm
« Reply #6 on: November 01, 2015, 05:51:44 am »
What sample input? In ideone I already fed my solution with the sample input and it succeed.
The one in the problem description:
Code: [Select]
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa
If your solution passes, how can I get the stacktrace? Your solution clearly triggers SIGSEGV a.k.a. EAccessViolation due to INDX increases to an extremely high value where the dynamic array can't hold anymore. Maximum size for a dynamic array is 2GB, your index is 4GB already when the crash happens.

FallingStar

  • Newbie
  • Posts: 6
Re: Problem trying to implement Dijkstra algorithm
« Reply #7 on: November 01, 2015, 09:09:26 am »
Weird... I tested this test case for thousands of times and every time it just gives the correct answer and ends with an exit code 0. Can you show me more of an evidence?

Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Problem trying to implement Dijkstra algorithm
« Reply #8 on: November 01, 2015, 03:12:47 pm »
Weird... I tested this test case for thousands of times and every time it just gives the correct answer and ends with an exit code 0. Can you show me more of an evidence?
https://asciinema.org/a/anh4hot59dm0qvua05br9fy0p

 

TinyPortal © 2005-2018