๐Ÿ”ข
Algorithms & Data
  • Overview
    • 1. Sort
      • Selection Sort
      • Bubble Sort
      • Insertion Sort
        • Insertion Sort:: singly linked list
          • Recursive
          • Using Array O(N), O(N)
          • Using Iteration O(N), O(1)
      • Quick Sort
      • Merge Sort
      • Heap Sort
      • Counting Sort
        • Counting Sort
          • Sort a String
        • Bucket Sort
        • Radix Sort
      • Topological Sort
    • 2. Data Structures
      • Array
      • Stack
      • Queue
      • Tree
        • PreOrder, InOrder, PostOrder
          • Transfer between each
          • Traverse
        • Binary Tree
          • Binary Search Tree
      • Graph
        • Data Structure
        • Traverse Graph
        • Detect a cycle in a Graph
          • DFS *
            • undirected clean code
          • Union Find
          • Count edges - undirected only
      • Linked List
      • Trie
        • Javascript
        • Java
      • Union Find
        • Detect Cycle with Disjoint-set Union Find
        • Kruskal Algorithm
      • Heap
      • Matrix
      • Union Find: Disjoint Set
    • 3. How to construct Algorithm? Paradigm
      • Greedy Algorithm
        • Prim
        • Dijkstra
        • Prim vs Dijkstra
      • Dynamic Planning Techique
      • Dynamic Planning
      • Divide And Conquer
      • Brute force
      • Shortest path
        • BFS
        • Dijkstra algorithm: directed, shortest path
      • MST (Minimum Spanning Tree)
        • Prim vs Digkstra
        • Prim, Kruskal Why? only undirected graph?
        • Kruskal's Algorithm: undirected
        • Prim's Algorithm: undirected
  • Algorithm Problems
    • Problem Sources
    • AlgoExpert
      • Hardest
        • Merge Sort
      • Hard
        • Primโ€™s Algorithm
        • Dijkstraโ€™s Algorithm
        • Kruskalโ€™s algorithm vs Primโ€™s algorithm
        • Topological Sort
        • Max Sum Increasing Subsequence
        • Find Nodes Distance K
        • Max Path Sum In Binary Tree
        • Validate Three Nodes
        • Same BST ?
        • Zigzag Traverse
        • Min Rewards
        • Largest Range
        • Subarray Sort
        • Four Number Sum
      • Medium
        • Missing Numbers
        • Beat Seat
        • Suffix Trie Construction
        • One Edit
        • Minimum Characters For Words
        • Reverse Words in String
        • Valid IP Addresses
        • Group Anagrams
        • Longest Palindromic Substring
        • Next Greater Element
        • Sort Stack โ‡’ recursive good -
        • Sunset Views
        • Balanced Brackets
        • Min Max Stack Construction
        • Three Number Sort โ‡’ counting sort or radix sort โ‡’ three pointer with in-place swap
        • Staircase Traversal โ‡’ it is like the number of ways to change
        • Phone Number Mnemonics โ‡’ can use word and index to create each case without concatenation
        • Power Set
        • Permutations -
        • Merging LinkedLists
        • Sum Of Linked Lists -
        • Remove Kth Node From End -
        • Linked List Construction - Doubly Linked List ?
        • Min Heap Construction
        • Valid Starting City
        • Task Assignment - use two pointer
        • Two Colorable - Graph
        • Minimum Passes Of Matrix
        • Cycle in Graph -
        • Remove Islands -
        • Youngest Common Ancestor
        • River Sizes -
        • Breadth First Search
        • Single Cycle Check
        • Union Find
        • Stable Internships
        • Kadaneโ€™s Algorithm
        • Levenshtein Distance
        • Min Number Of Coins For Change
        • Number Of Ways To Make Change
        • Number Of Ways To Traverse Graph
        • Max Subset Sum No Adjacent
        • Symmetrical Tree
        • Merge Binary Trees
        • Height Balanced Binary Tree
        • Find Successor
        • Binary Tree Diameter
        • Invert Binary Tree
        • Reconstruct Bst
        • Find Kth Largest Value In Bst
        • Min Height BST
        • BST Traversal
        • Validate Bst
        • BST Construction
        • Zero Sum Subarray + find indices of sub array
        • Merge Overlapping Intervals
        • First Duplicate Number
        • Array of Products
        • Longest Peak
        • Spiral Traverse
        • Monotonic Array
        • Move Element To End
        • Smallest Difference
        • Three Number Sum
      • Easy
        • Middle Node
        • Evaluate Expression Tree
        • Insertion Sort
        • Semordnilap
        • First Non Repeating Character
        • Generate Document
        • Run Length Encoding
        • Caesar Cipher Encryptor
        • Palindrome Check
        • Selection Sort
        • Bubble Sort
        • Find Three Largest Sum
        • Binary Search
        • Product Sum
        • Nth Fibonacci
        • Remove Duplicates From LinkedList
        • Tandem Bicycle
        • Class Photos
        • Minimum Waiting Time
        • Depth-first Search
        • Node Depths
        • Branch Sums
        • Find Closest Value In Bst
        • Non Constructible Change
        • Tournament Winner
        • Sorted Squared Array
        • Validate Subsequences
        • Two Number Sum
    • Daily Algorithms
      • 1. Topological Sort
      • 2. MST- Prim, Kruskal
      • 3. Cycle in a Graph
        • [Algo] Cycle in Graph (directed)
      • 4. Maximum sub array sum
        • Problem
        • Solutions
          • Brute Force
          • Divide And Conquer
          • Kadane's Algorithm - Dynamic
        • Empty Array allowed
        • Empty Array not allowed
        • Empty Array Not Allowed + circular
          • Double array:: O(N), O(N)
          • minimum subarray:: O(N), O(1)
      • 5. Detect a Cycle in a graph with a disjoint set (Union Find)
      • 6. Kruskal's Algorithm - Union Find
      • 7. Prim's Algorithm - Priority Queue
      • 8. Sort Array nlogn
      • 9. Shortest path - BFS
      • 10. Dijkstra algorithm
      • 11. Minimum spanning tree - points
      • 12. Minimum depth in a binary tree
      • 13. [Counting Sort]: H-index
      • 14. [shortest path]: Floyd-Warshall
      • 15. [Linked List]: reverse list
      • 16. [Linked List]: swap nodes in pairs
      • 17.[Linked List]: Merge k Sorted Lists
      • 18.[Linked list]:234. Palindrome Linked List
      • 19. [Linked List]: Linked List Cycle
      • 20. [Linked List] Reverse Linked List II
      • 21. [Linked List] sort a list - asc
      • 22. [Sort] Quick Sort
      • 23. [matrix] Spiral Matrix
      • 24. [matrix] Number of Islands
      • 25. [matrix] Valid Sudoku
      • 26. [matrix] Sudoku Solver
  • Top 75 LeetCode Questions to Save Your Time
    • Source
    • Problems
      • Interval
        • 56. Merge Intervals
        • 435. Non-overlapping Intervals
        • x 57. Insert Interval
      • Heap
        • x 295. Find Median from Data Stream
        • 347. Top K Frequent Elements
        • 23. Merge k Sorted Lists
      • Array
        • Untitled
        • 10. 11.ย Container With Most Water
        • 9. 15. 3Sum
        • 8. 33.ย Search in Rotated Sorted Array
        • 7. 153.ย Find Minimum in Rotated Sorted Array
        • x 6. 152. Maximum Product Subarray
        • 5. 53. Maximum Subarray
        • 4. 238. Product of Array Except Self
        • 1. Two Sums
        • 2. Best Time to Buy and Sell Stock
        • 3. Contains Duplicate
      • Binary
        • 190.ย Reverse Bits
        • 268. Missing Number
        • x 338.ย Counting Bits
        • 12. 191.ย Number of 1 Bits
        • 11. 371. Sum of Two Integers
      • Graph
        • x 417.ย Pacific Atlantic Water Flow
        • x 128. Longest Consecutive Sequence
        • 207.ย Course Schedule
        • 133. Clone Graph
        • 200. Number of Islands
      • Tree
        • x 297. Serialize and Deserialize Binary Tree
        • x 105. Construct Binary Tree from Preorder and Inorder Traversal
        • x 212. Word Search II
        • 211. Design Add and Search Words Data Structure
        • 208. Implement Trie (Prefix Tree)
        • 235.ย Lowest Common Ancestor of a Binary Search Tree
        • 230. Kth Smallest Element in a BST
        • 98.ย Validate Binary Search Tree
        • 572. Subtree of Another Tree
        • 297. Serialize and Deserialize Binary Tree ?
        • 102. Binary Tree Level Order Traversal
        • 124. Binary Tree Maximum Path Sum
        • 226. Invert Binary Tree
        • 100. Same Tree
        • 104. Maximum Depth of Binary Tree
      • Dynamic Programming
        • x 62.ย Unique Paths
        • x91. Decode Ways
        • 55. Jump Game
        • x 213. House Robber II
        • 198. House Robber
        • 377.ย Combination Sum IV
        • x 139. Word Break
        • 1143. Longest Common Subsequence
        • 300. Longest Increasing Subsequence
        • 322. Coin Change
        • 70. Climbing Stairs
        • 2023 0709 39.ย Combination Sum
      • String
        • x 76. Minimum Window Substring
        • 647.ย Palindromic Substrings
        • x 5. Longest Palindromic Substring
        • 125. Valid Palindrome
        • 20. Valid Parentheses
        • 49.ย Group Anagrams
        • 242. Valid Anagram
        • 5. Longest Palindromic Substring
        • 3. Longest Substring Without Repeating Characters
      • Matrix
        • x 48. Rotate Image
        • 79. Word Search
        • x 73. Set Matrix Zeroes
        • 54. Spiral Matrix
      • Linked List
        • 143. Reorder List
        • 19. Remove Nth Node From End of List
        • 23. Merge k Sorted Lists
        • 21. Merge Two Sorted Lists
        • 141. Linked List Cycle
        • 206. Reverse Linked List
  • Tip
    • Page 2
    • LinkedList
Powered by GitBook
On this page
  • Dijkstra
  • With Priority Queue
  • With visited Array
  • without visited Array
  1. Overview
  2. 3. How to construct Algorithm? Paradigm
  3. Shortest path

Dijkstra algorithm: directed, shortest path

PreviousBFSNextMST (Minimum Spanning Tree)

Last updated 1 year ago

๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ฐ„์„ ์— ๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๋Š” ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์—์„œ ์ตœ๋‹จ๊ฑฐ๋ฆฌ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ๋งŒ์•ฝ ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด ํ•˜๋‚˜์˜ ๊ฐ„์„ ์— ๋Œ€ํ•ด ์–‘๋ฐฉํ–ฅ์œผ๋กœ ์ด์–ด์ง€๋Š” ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋กœ ๋ณ€ํ™˜ํ•ด์•ผ ํ•œ๋‹ค. ์ฆ‰, ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋กœ ๋ฐ์ดํ„ฐ๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ํ˜•ํƒœ๋กœ ๋งŒ๋“ค์–ด์ค„ ํ•„์š”๊ฐ€ ์žˆ๋‹ค.

Dijkstra

Prim vs Dijkstra


Time: O(v^2 + e)

Space: O(V)

with out heap

function Node(v, predecessor, cost) {
  this.v = v;
  this.predecessor = predecessor;
  this.cost = cost;
}

function findMinimumCostVertex(nodes, visited) {
  let currentMinConst = Infinity;
  let here = -1;

  for (let vertex = 0; vertex < nodes.length; vertex++) {
    if (visited.has(vertex)) continue;

    const cost = nodes[vertex].cost;
    if (cost < currentMinConst) {
      currentMinConst = cost;
      here = vertex;
    }
  }

  return [here, currentMinConst];
}

function dijkstrasAlgorithm(start, edges) {

  const nodes = [];
  // initialize
  for (let i = 0; i < edges.length; i++) {
    const node = new Node(i, i, Infinity);
    nodes[i] = node;
  }

  nodes[start].cost = 0;
  const visited = new Set();

  while (visited.size !== edges.length) {
    const [here, currentMinCost] = findMinimumCostVertex(nodes, visited);
    // console.log(here, currentMinCost);

    // visited a vertex with Infinity > can not reach there
    if (currentMinCost === Infinity) {
      break;
    }
    
    const adj = edges[here] ?? [];
    for (const [there, cost] of adj) {
      if (visited.has(there)) continue;
      
      const prev = nodes[there].cost; // current min there cost
      const next = currentMinCost + cost;
      if (prev > next) {
        nodes[there].predecessor = here;
        nodes[there].cost = next;
      }
    }

    visited.add(here);

    // break;
  }

  const answer = [];
  for (let i = 0; i < edges.length; i++) {
     if (nodes[i].cost === Infinity) {
        answer[i] = -1;
     } else {
        answer[i] = nodes[i].cost;
     }

    console.log(nodes[i]);
  }

  return answer;
  
}

// Do not edit the line below.
exports.dijkstrasAlgorithm = dijkstrasAlgorithm;

With Priority Queue

With visited Array

Time: O((v + e)logv โ‡’ elogV)

Space: O(v)

using visited array not to add visited vertex

function Node(vertex, predecessor, cost) {
  this.vertex = vertex;
  this.predecessor = predecessor;
  this.cost = cost;
}

// O((V + E)logV => ElogV, usually E > V)
function dijkstrasAlgorithm(start, edges) {

  const dist = [];
  for (let vertex = 0; vertex < edges.length; vertex++) {
    dist[vertex] = new Node(vertex, vertex, Infinity);
  }
  
  const visited = new Set();
  dist[start].cost = 0;
  const minHeap = new Heap([], (a, b) => a.cost <= b.cost);
  minHeap.insert(new Node(start, start, 0));

  while (minHeap.size > 0) {
    const {
      vertex: here,
      predecessor,
      cost: currentCost,
    } = minHeap.remove();

    const adj = edges[here];
    for (const [there, incommingCost] of adj) {
      if (visited.has(there)) continue;
      
      const prev = dist[there].cost;
      const next = currentCost + incommingCost;
      if (prev > next) {
        dist[there].cost = next;
        dist[there].predecessor = here;
        
        minHeap.insert(new Node(there, here, next));
      }
    }

    console.log(minHeap.heap);

    visited.add(here);
  }
  const answer = [];
  for (let vertex = 0; vertex < edges.length; vertex++) {
    const node = dist[vertex];
    answer[vertex] = node.cost === Infinity ? -1 : node.cost;
  }

  return answer;
}

class Heap {
    constructor(arr, predicate = (a, b) => a <= b) {
        this.predicate = predicate;
        this.size = arr.length;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    insert(v) {
        this.heap.push(v);
        this.size++;

        this.siftDown(this.heap, 0, this.heap.length - 1);

    }

    remove(v) {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.size--;
        
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }

            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
        return heap;
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;

        while (left <= endIndex) {
            let min = left;
            const right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            if (this.predicate(heap[currentIndex], heap[min])) break;
            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }

        return heap;
    }

    swap(arr, a, b) {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }

}

// Do not edit the line below.
exports.dijkstrasAlgorithm = dijkstrasAlgorithm;

without visited Array

function Node(vertex, predecessor, cost) {
  this.vertex = vertex;
  this.predecessor = predecessor;
  this.cost = cost;
}

// O((V + E)logV => ElogV, usually E > V)
function dijkstrasAlgorithm(start, edges) {

  const dist = [];
  for (let vertex = 0; vertex < edges.length; vertex++) {
    dist[vertex] = new Node(vertex, vertex, Infinity);
  }
  
  const minHeap = new Heap([], (a, b) => a.cost <= b.cost);
  dist[start].cost = 0;
  minHeap.insert(new Node(start, start, 0));

  while (minHeap.size > 0) {
    const {
      vertex: here,
      predecessor,
      cost: currentCost,
    } = minHeap.remove();

    // we pu every connected nodes into heap
    // so we filter smallest cost from heap is bigger than or equal to current distance min
    // without using visited array
    if (dist[here].cost < currentCost) 
      continue;

    const adj = edges[here];
    for (const [there, incommingCost] of adj) {
      
      const prev = dist[there].cost;
      const next = currentCost + incommingCost;
      if (prev > next) {
        dist[there].cost = next;
        dist[there].predecessor = here;
        
        minHeap.insert(new Node(there, here, next));
      }
    }

    console.log(minHeap.heap);
  }
  
  const answer = [];
  for (let vertex = 0; vertex < edges.length; vertex++) {
    const node = dist[vertex];
    answer[vertex] = node.cost === Infinity ? -1 : node.cost;
  }

  return answer;
}

class Heap {
    constructor(arr, predicate = (a, b) => a <= b) {
        this.predicate = predicate;
        this.size = arr.length;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    insert(v) {
        this.heap.push(v);
        this.size++;

        this.siftDown(this.heap, 0, this.heap.length - 1);

    }

    remove(v) {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.size--;
        
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }

            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
        return heap;
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;

        while (left <= endIndex) {
            let min = left;
            const right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            if (this.predicate(heap[currentIndex], heap[min])) break;
            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }

        return heap;
    }

    swap(arr, a, b) {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }

}

// Do not edit the line below.
exports.dijkstrasAlgorithm = dijkstrasAlgorithm;

์ตœ๋‹จ๊ฒฝ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‹ค์ต์ŠคํŠธ๋ผ ์ดํ•ด์ง‘์ฃผ๋ณ€์ด ์ตœ๊ณ ์•ผ
Logo