Data Structures and Algorithms Diary

Dijkstra Algorithm in JavaScript, heap based fast implementation
Let’s pick up from where we left off and revisit the problem Dijkstra algorithm aims to solve. Input: directed graph G = (V, E) in adjacencylist representation, a source vertex s ∈ V, a length le ≥ 0 for each e ∈ E. Output: the true shortestpath distance to every vertex v from the source…

Dijkstra’s Algorithm in JavaScript, slow implementation
Dijkstra’s Algorithm is a handy tool for figuring out the shortest path in a connected directed graph where each connection has a nonnegative weight. If you’re familiar with Prim’s Minimum Spanning Tree, despite having different goals, you’ll observe that both employ a greedy strategy to carefully select the optimal/smallest distance path step by step. Note:…

Priority queue min heap implementation in JavaScript
Here’s what I’ve learned about the heap data structure. The invariant of the min/max heap is this: when represented in a binary tree, the parent node’s value is always smaller/bigger than or equal to its children. The root is always the smallest/biggest value of the heap when represented as a binary tree. The two most…

Graph data structure in JavaScript
Here’s what I’ve learned about the graph data structure. Let’s start. We will represent the graph as an adjacency list, which is an object (or a hash table) that maps each vertex to an array of its adjacent vertices. This is a simple and efficient way to store the graph structure in JavaScript. To add…