AlgoDaily - An Illustrated Guide to Dijkstra's Algorithm

Home > Data Structures and Algorithms 🚀 > Draw a Graph > An Illustrated Guide to Dijkstra's Algorithm

Dijkstra's algorithm takes significant computational time. The time complexity in a general case is O(V²), where V is the number of vertices. This is improved to O(E log V) (where E is the number of edges) if the graph representation is changed to adjacency lists. While a polynomial time complexity such as O(V²) would seem high, it is better than brute force algorithms which provide much higher computational times.

You can find the full working implementation here:

xxxxxxxxxx
dijkstra(graph, "a", "f");
 
const graph = {
  a: { b: 5, c: 2 },
  b: { a: 5, c: 7, d: 8 },
  c: { a: 2, b: 7, d: 4, e: 8 },
  d: { b: 8, c: 4, e: 6, f: 4 },
  e: { c: 8, d: 6, f: 3 },
  f: { e: 3, d: 4 },
};
​
const printTable = (table) => {
  return Object.keys(table)
    .map((vertex) => {
      var { vertex: from, cost } = table[vertex];
      return `${vertex}: ${cost} via ${from}`;
    })
    .join("\n");
};
​
const tracePath = (table, start, end) => {
  var path = [];
  var next = end;
  while (true) {
    path.unshift(next);
    if (next === start) {
      break;
    }
    next = table[next].vertex;
  }
​

Programming Categories

Popular Lessons