Dijkstra’s algorithm is the most popular algorithm to find the shortest paths from a certain vertex in a weighted graph.In fact, the algorithm will find the shortest paths to every vertex from the start vertex.The algorithm takes both greedy and dynamic programming approach that it will try to find local optimum paths first and use them to find the shortest paths.Let’s take a look at how it works! How does Dijkstra’s algorithm work? Let’s say we need to find the shortest path from node A to node E. There are five nodes and each edge is weighted with the cost READ MORE
Tag: algorithm
Intro to Union-Find Data Structure
Union-Find is a data structure that mimics tree data structure except that nodes point to their parent instead of children. The union-find is very useful for set operations such as the following.1. find – find the root of the current node2. same component – check if two trees have the same root node. (belongs to the same set)3. union (merge) – merge two trees (sets) into one Such operations are very useful for problems like connected components – each node belongs to only one connected component – and vertex coloring. The union-find is useful for algorithms such as minimum-spanning tree READ MORE
How to detect a loop (cycle) in a linked list
Traversing linked list is easy but what would happen if there is a cycle in the linked list?It will just fall into an infinity loop if traversing is implemented without a cycle prevention code.Thankfully, there is already a known algorithm for this kind of problem. How to detect if a cycle exists? Suppose there is a linked list that has a cycle like below.Now the question is how to detect the cycle. Let’s first think about what would happen if there is a cycle. Iterating linked list typically happens in a while loop like these steps. Check if the node READ MORE
Intro to Topological Sort
Topological sort is an important algorithm in DAG – directed acyclic graphs. It orders each vertex in line from left to right such that left most vertex could be considered as the highest level or root or entrance of the graph and rightmost as the lowest of the graph. In the end, topological sort tells you the order of vertices you need to go through from one node to the other without missing any middle vertices. There could be multiple topological sorts in the same graph. Let’s take a look at an example for a better understanding Course Prerequisite Example READ MORE
Intro to Depth First Search (DFS)
Depth first search is one of the popular graph traversal algorithms that work well for certain purposes.As you can infer from the name DFS is quite different from BFS – breadth first search.Therefore the applications of DFS are different from BFS.In this post, I am going to discuss how DFS works with examples.Please refer to my other post of BFS if you are interested in. How does DFS work? I am going to start by explaining DFS by comparing it with BFS.Please note that BFS searches all the neighbors at the same level or degree before you move to the READ MORE
Intro to Breadth First Search (BFS)
When dealing with a graph it might be necessary to traverse the graph.Graph traversal is a systemic method to traverse the graph.Breadth first search is one of the most popular graph traversal algorithms that work very well for certain purposes.Today, I am going to introduce breadth first search in this post. How does breadth first search traverse? BFS is a graph traversal algorithm to visit vertices from one starting point in a certain way.How does it visit other nodes? It first visits its nearest neighbors and processes them before reaching any further nodes.And it marks nodes as it visits so READ MORE
Intro to Graphs
A graph is an abstract representation of a complex system such as networks, human relationships, and any organization.A graph is very important because it can represent and simplify any complex relationships in a visual format.It is pretty amazing that messy applied problems often could be described with simple and classical graph properties. In this post, I am going to discuss some popular graphs and brief examples. Graph Examples A graph G can be represented as a set of vertices and edges which can be said as G = (V, E)Now, let’s take a look at various graphs and their properties. READ MORE
Intro to Mergesort Algorithm
Mergesort is a sorting algorithm, a classic example of a divide and conquer sorting algorithm.Divide and conquer is a technique to solve the problem by dividing it into smaller subsets which should be simple to easier to deal with.The result of small problems now should help to solve bigger subsets and eventually the entire problem.Let’s take a look at how mergesort works. Mergesort Algorithm The following is the steps for mergesort algorithm Recursively divide the array into smaller sub-arrays until each array has a single element. Recursively merge sub-arrays with sorted order until all the sub-arrays are merged. Note that READ MORE
Intro to Quicksort Algorithm
Quicksort is one of the most popular sorting algorithms.Although there are quite a few sorting algorithms such as mergesort, heapsort quicksort has a unique property that is noteworthy.In general, quicksort performs better than others due to its property under a certain condition. Let’s take a look at the basics of quicksort! How does quicksort work? Quicksort sorts the array by partitioning the array recursively which is one of divide and conquer sorting algorithms.Quicksort first selects a random element and partitions the elements based on the selected element which is called a pivot.All the elements that are less than the pivot READ MORE
Intro to Binary Search Algorithm
Let’s say there is an unsorted array and you need to find certain values.How would you search for those values? You can’t avoid iterating the entire array every time you are searching since the array is unsorted.Wouldn’t this be a very inefficient way of searching?It may be fine if the size of the array is pretty small. However, what if there are one million elements in the array?You probably do not want to iterate one million elements every time you search because it’s a waste of time. Binary search algorithm is a very efficient search algorithm.It requires the array to READ MORE