Talk:Dijkstra's algorithm: Difference between revisions

Line 261:

: The Go code is fine for what it's doing, but it's best not to draw conclusions about the performance based only on the current test case. --[[User:Ledrug|Ledrug]] 06:55, 10 December 2011 (UTC)

:: All very good points. Constructing the edge list took 133ms, constructing the linked representation took 225ms, and then the path search took only 7ms. It does seem likely that the graph wouldn't be fully connected. Spoon, thanks for the simplifications to the Go code! —[[User:Sonia|Sonia]] 00:20, 11 December 2011 (UTC)

== Bug in C implementation ==

The line:

int i = h->index[v] || ++h->len;

Does not evaluate correctly the expression. If h->index[v] == 0 then ++h->len is not assigned to i, instead 1 is assigned. In theory the compiler should assign the right side expression to i but is not working with gcc. For example, the graph:

add_edge(g, 'a', 'b', 1);

add_edge(g, 'b', 'c', 1);

add_edge(g, 'c', 'd', 1);

add_edge(g, 'd', 'e', 1);

add_edge(g, 'e', 'f', 1);

add_edge(g, 'f', 'a', 1);

add_edge(g, 'a', 'g', 2);

add_edge(g, 'g', 'b', 2);

add_edge(g, 'c', 'g', 2);

add_edge(g, 'g', 'd', 2);

add_edge(g, 'e', 'g', 2);

add_edge(g, 'f', 'g', 2);

dijkstra(g, 'a', 'e');

print_path(g, 'e');

Will output '5 agde' and is wrong because path '4 abcde' is shorter. Next line fixes the problem:

int i = h->index[v] ? h->index[v] : ++h->len;

== Directed vs undirected graphs ==