ball-blog
  • Welcome, I'm ball
  • Machine Learning - Basic
    • Entropy
    • Cross Entropy
    • KL-Divergence
    • Monte-Carlo Method
    • Variational Auto Encoder
    • SVM
    • Adam Optimizer
    • Batch Normalization
    • Tokenizer
    • Rotary Positional Encoding
    • Vector Quantized VAE(VQ-VAE)
    • DALL-E
    • Diffusion Model
    • Memory Layers at Scale
    • Chain-of-Thought
  • Einsum
  • Linear Algebra
    • Linear Transformation
    • Determinant
    • Eigen-Value Decomposition(EVD)
    • Singular-Value Decomposition(SVD)
  • AI Accelerator
    • CachedAttention
    • SGLang
    • CacheBlend
  • Reinforcement Learning
    • Markov
  • Policy-Improvement Algorithm
  • Machine Learning - Transformer
    • Attention is All you need
    • Why do we need a mask in Transformer
    • Linear Transformer
    • kr2en Translator using Tranformer
    • Segment Anything
    • MNIST, CIFAR10 Classifier using ViT
    • Finetuning PaliGemma using LoRA
    • LoRA: Low-Rank Adaptation
  • EGTR: Extracting Graph from Transformer for SGG
  • Machine Learning - Mamba
    • Function Space(Hilbert Space)
    • HIPPO Framework
    • Linear State Space Layer
    • S4(Structures Space for Sequence Model)
    • Parallel Scan Algorithm
    • Mamba Model
  • Computer System
    • Memory Ordering: Release/Acquire 1
    • Memory Ordering: Release/Acquire 2
    • BUDAlloc
    • Lock-free Hash Table
    • Address Sanitizer
  • App development
    • Bluetooth connection in linux
    • I use Bun!
    • Using Tanstack-query in Frontend
    • Deploying AI Service using EC2
  • Problem Solving
    • Bipartite Graph
    • Shortest Path Problem in Graph
    • Diameter of a Tree
  • Scribbles
Powered by GitBook
On this page
  • Shortest Path Problem
  • Algorithms

Was this helpful?

Edit on GitHub
  1. Problem Solving

Shortest Path Problem in Graph

Last updated 3 months ago

Was this helpful?

Shortest Path Problem

Given a graph and start/end point, finding the shortest path(evaluating the edge's weight as distance) is called Shortest Path Problem.

Algorithms

Dijkstra Algorithm

Dijkstran algorithm is used when graph doesn't have any negative edges.

We use two hashtables:

  • "shortest-length" hashtable to store the shortest distance from starting point to each nodes.

  • "is-visited" hashtable to store if the node is visited.

Pseudo code for Dijkstra algorithm is as follows:

1. set starting point entry in "shortest-length" hashtable to zero, 
and INF for others

2. visit staring node.

3. update visiting node's neighbor entry in "shortest-length" hashtable
using edge info nearby visiting node.

4. update "is-visited" hashtable

5. among not-visited nodes, pick the node that has 
shortest length between the starting node. Go to 3., visiting the chosen node.

Bellman-Ford Algorithm

Bellman-Ford algorithm can be applied to graphs that has negative edges, and also verify if there are negative-loop.

We use a single hashtable:

  • "shortest-length" hash that stores the shortest distance from starting point to each nodes.

Pseudo code for Dijkstra algorithm is as follows:

1. set starting point entry in "shortest-length" hashtable to zero, 
and INF for others

2. 
for i in range(V-1): 
    go through every edges, and update the "shortest-length" hashtable.
    
After the iteration, "shortest-length" hashtable will have shortest-path from the starting point.

If you do one more iteration, and if the "shortest-length" hashtable changes,
it means that there is a negative-loop.
Figure of a graph with positive edges
Dijkstra algorithm GIF from
Bellman-Ford algorithm figure from
https://medium.com/@chuncaohenli/animated-algorithm-a9fa339d44c
https://www.prepbytes.com/blog/graphs/bellman-ford-algorithm/