Dijkstra's algorithm: Difference between revisions
Content added Content deleted
m (Added Sidef) |
|||
| Line 1,552: | Line 1,552: | ||
This version finds all shortest paths, and for this example completes in two thirds the time of the other J implementation. |
This version finds all shortest paths, and for this example completes in two thirds the time of the other J implementation. |
||
This algorithm first translates the graph representation to a cost connection matrix, with infinite cost for unconnected nodes. Then we use a summing variation on transitive closure to find minimal connection costs for all nodes, and extract our best price from that. If our desired nodes are connected, we then search for paths which satisfy this best (minimal) price constraint: We repeatedly find all connections from our frontier, tracking path cost and discarding paths which have a cost which exceeds our best price. When a path reaches the end node, it is removed and remembered. |
This algorithm first translates the graph representation to a cost connection matrix, with infinite cost for unconnected nodes. Then we use [[Floyd-Warshall_algorithm#J|a summing variation on transitive closure]] to find minimal connection costs for all nodes, and extract our best price from that. If our desired nodes are connected, we then search for paths which satisfy this best (minimal) price constraint: We repeatedly find all connections from our frontier, tracking path cost and discarding paths which have a cost which exceeds our best price. When a path reaches the end node, it is removed and remembered. |
||
=={{header|Java}}== |
=={{header|Java}}== |
||