What problem does Dijkstras algorithm solve?
Dijkstra’s algorithm finds shortest paths in a graph from all vertices to a given vertex. • Is the vertex cover problem known to be NP-complete, or is that only conjectured? Is it known whether the vertex cover problem is in the class P? Is it known whether the vertex cover problem is in the class NP? The vertex cover problem is known to be NP-complete. (We proved it in class.) The vertex cover problem is known to be in NP. (There is a nondeterministic polynomial time algorithm to solve it.) If P and NP are different classes, then the vertex cover problem is not in P. However, nobody knows whether P and NP are different; that is only conjectured. So it is only a conjecture that leads to the conclusion that the vertex cover problem is not in P. • Do problem 17.2-5. This one I will leave to you. If you solved the Professor Midas problem above it, you should have no problem with this one. • The partition problem is as follows. You are given a list of positive integers. You would like to c
