Content deleted Content added
Tameralkuly (talk | contribs) Isn't there something wrong in the example ? |
|||
Line 153:
All of the algorithms have do |V|-1 iterations. The adjacency matrix implementation takes O(''V'') time to find the minimum, whereas the other implementations '''including the fibonnaci heap?''' take O(log(''V'')) time. As described above, all of vertices adjacent to the last vertex added are updated. There are, on average, E/V adjacent vertices. The adjacency matrix '''and fibonnaci heap ?''' take constant time to update the minimum distance, whereas the binary heap takes log(V) time. The [[Fibonacci heap]] is significantly faster when the graph is dense enough that ''E'' is <math>\Omega</math>(''V''log ''V''). --gatoatigrado <!-- ~~~ -->
== Isn't there something wrong in the example ? ==
Please be certain about this sentence : "vertex '''D''' has been arbitrarily chosen as a starting point." , i think the starting point is '''A''' not '''D''', if i am right , then you have to change the description of the second step in addition to the first step : i suggest the following :
This is our original weighted graph. This is not a tree because the definition of a tree requires that there are no circuits and this diagram contains circuits. A more correct name for this diagram would be a graph or a network. The numbers near the arcs indicate their weight. None of the arcs are highlighted, and vertex '''A''' has been arbitrarily chosen as a starting point.
The second chosen vertex is the vertex nearest to '''A''': '''D''' is 5 away, '''B''' is 7. Of these, 5 is the smallest, so we highlight the vertex '''D''' and the arc DA.
| |||