Coding with Thong

Tag: graph

  • 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 adjacency-list representation, a source vertex s ∈ V, a length le ≥ 0 for each e ∈ E. Output: the true shortest-path 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 non-negative 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:…

  • 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…