Table of Contents Definition Finding the Minimum Spanning Tree Kruskal’s Algorithm Prim’s Algorithm Minimum spanning trees are undirected graphs that connect all of the vertices such that there are no redundant edges and the total weight is minimized. They are useful for finding the shortest path between two points in a graph. Useful application of MSTs include
network design: it is useful to know the least expensive path with respect to either latency or resource cost for telecommunications networks, transportation networks, or electrical grids. approximation algorithms: MSTs can be used to approximate the solution to the traveling salesman problem. clustering: MSTs can be used to cluster data points in a graph. image segmentation: MSTs can be used to segment images into smaller regions. Definition Let \(G\) be a connected, undirected graph with edges \(E\), vertices \(V\), and edge weights \(w\). A minimum spanning tree is a subset \(T \subseteq E\) that connects all of the vertices such that the total weight is minimized. The original graph \(G\) is shown below.
Table of Contents Definition Bellman-Ford Shortest Paths on a DAG Dijkstra’s Algorithm When you hear the term shortest path, you may think of the shortest physical distance between your current location and wherever it is you’re going. Finding the most optimal route via GPS is one of the most widely used mobile applications. Physical paths are not the only types we may wish to find a shortest path for. Other examples include: