Anonymous user
Talk:Dijkstra's algorithm: Difference between revisions
→Directed vs undirected graphs: new section
(→Why is this a draft task?: There, I fixed it.) |
(→Directed vs undirected graphs: new section) |
||
Line 26:
: 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)
== Directed vs undirected graphs ==
Dijkstra's algorithm can work on directed or undirected graphs. (An undirected graph can be converted into an equivalent directed graph, where for each edge in the original graph, you have two equal-weighted edges in opposite directions.) The example that the task asks the user to solve does not directly mention that it is an undirected graph; however, the solutions assume that it is an undirected graph, which is okay assuming that that was what was intended I guess. However, to be general, each solution's main algorithm implementing function should still be able to accept an adjacency matrix that is not an undirected graph. --[[User:Spoon!|Spoon!]] 08:43, 26 January 2012 (UTC)
| |||