In the presence of negative edge weights, the algorithm used for accomplishing this task depends on the number of relaxation operations and has average complexity given by the product of the number of edges and vertices.
One algorithm for this task is characterized by propagating waves of RAISE and LOWER states. In the absence of negative cycles, this task can be achieved by a cubic-order dynamic programming algorithm, which subdivides this task into intermediate vertices and computes a bottom-up metric from the connection matrix; that is the Floyd-Warshall algorithm. In the presence of negative edge weights, the algorithm used for accomplishing this task depends on the number of relaxation operations and has average complexity given by the product of the number of edges and vertices. In addition to the Bellman-Ford algorithm another method for approaching this task progressively closes the nearest node from an "open" set and adds its adjacent nodes, while computer games occasionally employ navigation meshes. For 10 points, name this process executed by algorithms like A* and Dijkstra's algorithm, which is also the subject of the traveling salesman problem.
One algorithm for this task is characterized by propagating waves of RAISE and LOWER states.
pathfinding [accept equivalents like shortest path]