Lazarus
Free Pascal => Beginners => Topic started by: FallingStar 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 (nonzero 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

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

The second link is a link to the problem I'm trying to solve that uses the Dijkstra algorithm, not to the algorithm itself.

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

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

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?

What sample input? In ideone I already fed my solution with the sample input and it succeed.
The one in the problem description:
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.

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?

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