# Lazarus

## Free Pascal => Beginners => Topic started by: FallingStar on October 30, 2015, 02:50:11 pm

Title: Problem trying to implement Dijkstra algorithm
Post by: FallingStar on October 30, 2015, 02:50:11 pm
My solution: http://ideone.com/Dnh5Zw
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:
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
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: Thaddy on October 30, 2015, 03:23:19 pm
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 ;)
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: FallingStar 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.
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: Leledumbo 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:5555   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?
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: Thaddy 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).
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: FallingStar 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.

Don't you understand the difference between theory and exercise?
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: Leledumbo 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]
`14gdansk22 13 3bydgoszcz31 13 14 4torun31 32 14 1warszawa22 43 12gdansk warszawabydgoszcz 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.
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: FallingStar 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?
Title: Re: Problem trying to implement Dijkstra algorithm
Post by: Leledumbo 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