Back to For Beginners

Shortest path algorithm with linked list

For Beginners

Started by Carolina June 20, 2005 07:42 PM

1 comment, last by Carolina 18 years, 10 months ago

Carolina

176

Author

June 20, 2005 07:42 PM

Hi!Here I am again,in trouble as always XD My mission is to implement a version of Dijkstra´s Algorithm(that finds the shortest path between two points) using a Linked List instead of the commom matrix of distance values. I only want to know how any of you would implement the "relaxation" part of the algorithm(that part in which it is made a comparison between a vector of distances D and a matrix of values input by the user). Thanks in advance!

hplus0603

11,916

June 20, 2005 07:57 PM

I really wouldn't implement it using a linked list. A hash-map from node ID to cost, or a vector (or a vector of vector) maybe, but never a linked list. Finding the right node to update would be O(N) and would cache poorly (because each node can be a new cache line).

enum Bool { True, False, FileNotFound };

Carolina

176

Author

June 20, 2005 08:20 PM

Well,I wouldn´t implement it using a linked list either,but my teacher is nuts and he wants it delivered today!Whoa,I´m such a lucky student XD