Optimisation algorithms：練習問題

A programmer uses Dijkstra's shortest path algorithm to find the quickest route between two nodes in a network. Which of the following best describes how the algorithm handles a vertex once it has been 'visited'?

A specific graph-traversal algorithm is used to find the shortest path between a starting node and all other nodes in a weighted graph with non-negative edge weights. During the execution, the algorithm maintains a set of unvisited nodes and assigns each a 'tentative distance' value. Which of the following best describes the update step when the algorithm processes an unvisited neighbor \(V\) from the current node \(U\)?

An algorithm must find the shortest path between two nodes in a weighted graph with only positive edge weights. Which algorithm is most appropriate, and what is the typical graph-traversal strategy it employs?

Dijkstra's algorithm is used to find the shortest path in a graph. What is a specific requirement for the edge weights in the standard version of this algorithm?

In the context of optimisation algorithms, why might a heuristic method be used instead of an exact algorithm like Dijkstra's?

Dijkstra's algorithm is a well-known optimisation algorithm. Describe the specific condition that must be met by the edge weights in a graph for the standard version of Dijkstra's algorithm to successfully find the shortest path.

Explain the significance of Dijkstra's algorithm being categorized as an optimisation algorithm and state the primary goal it achieves when applied to a weighted graph.

A student is tracing Dijkstra's algorithm on a graph with nodes A, B, and C. If the current shortest distance to B is 10 and an edge (A, B) with weight 4 is processed while A has a distance of 3, describe the update step performed by the algorithm.

A researcher is using Dijkstra's algorithm to find the shortest path in a weighted graph representing a local delivery network.

(a) Describe the data structures required to implement Dijkstra's algorithm efficiently.
(b) Explain why Dijkstra's algorithm may fail to find the correct shortest path if the graph contains edges with negative weights.

Dijkstra's shortest path algorithm is a key optimisation algorithm for weighted graphs.

(a) Outline the general steps involved in Dijkstra's algorithm, focusing on how 'tentative distances' are updated.

(b) Explain the importance of using a priority queue (or similar data structure) to manage unvisited nodes to improve time complexity.

(c) Why does Dijkstra's algorithm require all edge weights to be non-negative? Explain what would happen if a negative edge weight were present.