Kruskal's algorithm will find a minimum spanning tree, even if the graph contains edges with negative weights. Prim's algorithm will find a minimum spanning tree, even if the graph contains edges with negative weights. Dijkstra's algorithm can be used to find the longest path in a graph by (only) changing the min-heap to a max-heap and using Extract-Max instead of Extract-Min Dijkstra's algorithm can be used to solve the single-destination shortest paths problem in a directed graph by (1) creating Grev which is the same as G with all of the edges reversed and (2) rumning Dijkstra's algorithm from the target destination. Given a cut (S,VS) of an undirected graph G, there is always exactly one light edge that crosses the cut. In a graph G where all of the edge weights are distinct, if an edge is the heaviest edge on a cycle in G, then that edge will be in every minimum spanning tree of G. In a graph G, if an edge e is not part of a any cycle in G, it will be in every minimum spanning tree of G. Breadth-first search can be used instead of Dijkstra's algorithm to find the shortest cost path between two nodes when all edges in the graph have the same weight. During Dijkstra's algorithm's search for a shortest path, a node's estimate of its distance can go up and down, but it will eventually settle on the correct shortest path cost. Let G be a graph with strictly positive edges and let T be an MST of G. Suppose you double the weight of every edge in the graph G, then T is still an MST of G; i.e., the edges of the MST remain the same