29 août 20193 août 2020 Bastien Pasdeloup When running Dijkstra's algorithm on a weighted graph from vertex u, what following conditions are (independently) sufficient to guarantee that the Dijktra's algorithm outputs are the shortest paths from vertex u to the accessible vertices of the graph? The input graph is connected. The input graph contains only nonnegative weights. The input weighted graph is a tree. What following property best describes the functioning of Dijkstra's algorithm, starting from a vertex u? We explore vertices as we would do for a BFS. We explore vertices by increasing the hops from u in the graph. We explore vertices by increasing the distance from u in the graph. The Dijkstra's algorithm maintains two data structures along the process. What are they? An estimation of the order of the graph and an estimation of the size of the graph. The list of explored vertices and an estimation of the distances from u to the other vertices of the graph. The list of explored vertices and the list of explored edges. Time is Up!
