In 1956 the Dutch computer scientist Edsger Dijkstra conceived an algorithm that solved the single-source shortest path problem for a graph with nonnegative edge path costs.
The algorithm, which is based on a graph that is made up of paths that intersect at different nodes, determines the path with the lowest cost between an initial node and every other node. Any two nodes are connected by an directed edge, and the path between any two nodes is made up of at least one edge.
As a result, Dijkstra’s algorithm is now often used to solve common real world routing problems such as finding the shortest path between two cities given certain constraints such as distance and direction.
In the world of computing Dijkstra's Algorithm is now known to be a greedy algorithm. This is because this algorithm makes the most efficient choice at each step. Therefore, the idea behind this rational is that a series of optimal decisions will lead to an optimal final decision. Thus, Dijkstra's algorithm is like a function that computes the optimal cost/path between the origin and all other nodes on the graph.
In the world of computing Dijkstra's Algorithm is now known to be a greedy algorithm. This is because this algorithm makes the most efficient choice at each step. Therefore, the idea behind this rational is that a series of optimal decisions will lead to an optimal final decision. Thus, Dijkstra's algorithm is like a function that computes the optimal cost/path between the origin and all other nodes on the graph.
No comments:
Post a Comment