Visualizing Dijkstra’s Single Source Shortest Path Dijkstra’s Algorithm can be applied to either a directed or an undirected graph to find the shortest path to each vertex from a single source. It can only be used with non-negative edge weights. A table is generated to track the distance from the source (S) vertex. The distance to each vertex is initialized to infinity except for the source itself. Another variable, π, is used to track the previous vertex from which the specified vertex was reached. Dijkstra’s algorithm starts with the source, S, and relaxes the edges that are connected directly to
Tag: Algorithms
Exploring Shortest Paths The Bellman-Ford algorithm finds the shortest path to each vertex in the directed graph from the source vertex. Unlike Dijkstra’s algorithm, Bellman-Ford can have negative edges. To begin, all the outbound edges are recorded in a table in alphabetical order. Like Dijkstra’s algorithm, a table recording the distance to each vertex and the predecessor of each vertex is created. The distances for each vertex, except the source vertex, is initialized to infinity. Distance is represented by the variable d and the predecessor is represented by the variable π. The Bellman-Ford algorithm will iterate through each of the edges.
Visual Explanation of Johnson’s Algorithm Johnson’s algorithm finds the shortest paths between all pairs of vertices in a directed graph. It converts negative edge weights into non-negative edge links. It does this by using the Bellman-Ford algorithm to remove all negative weights. It then allows Dijkstra’s algorithm to be used on the new graph. Let’s start with an example. Since this graph contains negative edges, Dijkstra’s algorithm cannot be applied to it yet. To begin, the edge links must be transformed to contain non-negative numbers. Johnson’s algorithm starts off by selecting a source vertex. The problem with choosing an existing
Navigating Line Segments If you’re given a problem to find out whether two line-segments intersect, there is an easy approach to this. It involves finding the orientation of the line segments. If they’re different, they intersect. Each line segment has a start-point and an end-point. Our first line will be represented by (a1,b1) and our second line will be represented by (a2,b2). To test if they intersect, we need to verify the following condition: What does this mean exactly? Let’s jump into an example and find out. It’s clear to us that the two line-segments intersect, but it’s not clear
A Visual Guide to Graham’s Scan Graham’s scan is a method for finding the convex hull that encompasses all points on the plane. Below you’ll see an example of a convex hull. Graham’s scan starts by finding the point with the lowest y coordinate. If there are multiple points on the y-coordinate, the point with the smallest x-value is chosen. The points are sorted by polar angles in counterclockwise rotation. Graham’s scan utilizes the stack. Points are pushed onto the stack. If the point is not part of the convex hull, the point is popped from the stack. Let’s look
Finding the Closest Pair of Points on a Plane If we’re given a set of points that lie on a plane, how can we figure out which pairs are the closest pair of points on the plane? The points are frequently stored in an array. One approach is to take the divide and conquer method. How? By following the steps below: Count the number of points on the plane. Divide the points into two equal groups and draw a line through the middle. If there are an odd number of points, a line will go through at least one of the
A Visual Guide to Voronoi Graph & Delaunay Triangulation Voronoi diagrams help us find the closest points from an arbitrary point. Let’s start by displaying a set of points on a plane. The Voronoi diagram draws boundaries between each of those points. Around each point, regions will develop called the Voronoi regions. Let’s see how we would draw those boundaries. Each boundary should be in the middle of two points. Let’s begin by drawing a boundary between point 1 and point 2. The boundary should be directly in the middle separating the two points. Let’s move to creating a boundary
Understanding Maximum Independent Set Visually Given a graph, a subset of the vertices is an independent set if there are no edges between the vertices in the subset. Let’s take a look at a quick example to see what this means. We can see that there is an edge between the following points: Points 1 and 2 Points 1 and 3 Points 1 and 4 Points 2 and 3 Points 2 and 5 Points 3 and 5 Points 4 and 5 Points 4 and 6 Points 5 and 6 When trying to find the maximum independent set, we’ll try to
Understanding Minimum Vertex Cover Visually When trying to find the minimum vertex cover, you’re going to be trying to find the minimum number of vertices that will include all the edges. We can start with the densest vertex on the graph and hope that we get lucky. We can choose vertex 3 next. Through some trial and error, you’ll see that you will have to choose 2 points from points 1, 2, and 3 regardless of which point you choose next. Finally, we must choose either vertex 4 or vertex 6. We’ll choose vertex 4. Since all the edges are
Visual Explanation of Maximum Clique Maximum clique is a technique used to find the largest vertex cluster where each vertex is connected to each other. Let’s look at an example. We’ll examine each vertex and see what the greatest cluster of the following graph will be. Let’s look at the first vertex. Vertex 1 is connected to vertices 2, 4, and 6. We need to make sure that each of those vertices has a connection to one another as well. Is vertex 2 connected to vertex 4? Yes Is vertex 2 connected to vertex 6? Yes Is vertex 4 connected to