| Share this post! | Vote this! |
|
Dijkstra's Algorithm is a graph-search algorithm that finds the shortest
path between two Vertices on a weighted Graph. For Dijkstra's
algorithm, we assume that all distances are positive.
So how exactly does this algorithm work? Basically, we initialize all the distances to infinity, except for the root Vertex which is initialized to 0. We then traverse the Graph from the starting point towards the end point. When we hit a Node, we evaluate the cumulative distance to that Node, which means the distance recorded at the previous Node plus to the distance to the current Node. So if we have A-->B weighted at 5 and B-->C weighted at C, B would record the distance 5, and C would record the distance 8. The reason we initialize to infinity is that the first time we hit that Node, everything will be less than infinity so the first distance will be stored at that Node. more...
So how exactly does this algorithm work? Basically, we initialize all the distances to infinity, except for the root Vertex which is initialized to 0. We then traverse the Graph from the starting point towards the end point. When we hit a Node, we evaluate the cumulative distance to that Node, which means the distance recorded at the previous Node plus to the distance to the current Node. So if we have A-->B weighted at 5 and B-->C weighted at C, B would record the distance 5, and C would record the distance 8. The reason we initialize to infinity is that the first time we hit that Node, everything will be less than infinity so the first distance will be stored at that Node. more...
0 comments:
Post a Comment