scrapbook
  • "Unorganized" Notes
  • The Best Public Datasets for Machine Learning and Data Science
  • Practice Coding
  • plaid-API project
  • Biotech
    • Machine Learning vs. Deep Learning
  • Machine Learning for Computer Graphics
  • Books (on GitHub)
  • Ideas/Thoughts
  • Ziva for feature animation: Stylized simulation and machine learning-ready workflows
  • Tools
  • 🪶math
    • Papers
    • Math for ML (coursera)
      • Linear Algebra
        • Wk1
        • Wk2
        • Wk3
        • Wk4
        • Wk5
      • Multivariate Calculus
    • Improving your Algorithms & Data Structure Skills
    • Algorithms
    • Algorithms (MIT)
      • Lecture 1: Algorithmic Thinking, Peak Finding
    • Algorithms (khan academy)
      • Binary Search
      • Asymptotic notation
      • Sorting
      • Insertion sort
      • Recursion
      • Solve Hanoi recursively
      • Merge Sort
      • Representing graphs
      • The breadth-first search algorithm
      • Breadth First Search in JavaScript
      • Breadth-first vs Depth-first Tree Traversal in Javascript
    • Algorithms (udacity)
      • Social Network
    • Udacity
      • Linear Algebra Refresher /w Python
    • math-notes
      • functions
      • differential calculus
      • derivative
      • extras
      • Exponentials & logarithms
      • Trigonometry
    • Probability (MIT)
      • Unit 1
        • Probability Models and Axioms
        • Mathematical background: Sets; sequences, limits, and series; (un)countable sets.
    • Statistics and probability (khan academy)
      • Analyzing categorical data
      • Describing and comparing distributions
      • Outliers Definition
      • Mean Absolute Deviation (MAD)
      • Modeling data distribution
      • Exploring bivariate numerical data
      • Study Design
      • Probability
      • Counting, permutations, and combinations
      • Binomial variables
        • Binomial Distribution
        • Binomial mean and standard deviation formulas
        • Geometric random variable
      • Central Limit Theorem
      • Significance Tests (hypothesis testing)
    • Statistics (hackerrank)
      • Mean, Medium, Mode
      • Weighted Mean
      • Quartiles
      • Standard Deviation
      • Basic Probability
      • Conditional Probability
      • Permutations & Combinations
      • Binomial Distribution
      • Negative Binomial
      • Poisson Distribution
      • Normal Distribution
      • Central Limit Theorem
      • Important Concepts in Bayesian Statistics
  • 📽️PRODUCT
    • Product Strategy
    • Product Design
    • Product Development
    • Product Launch
  • 👨‍💻coding
    • of any interest
    • Maya API
      • Python API
    • Python
      • Understanding Class Inheritance in Python 3
      • 100+ Python challenging programming exercises
      • coding
      • Iterables vs. Iterators vs. Generators
      • Generator Expression
      • Stacks (LIFO) / Queues (FIFO)
      • What does -1 mean in numpy reshape?
      • Fold Left and Right in Python
      • Flatten a nested list of lists
      • Flatten a nested dictionary
      • Traverse A Tree
      • How to Implement Breadth-First Search
      • Breadth First Search
        • Level Order Tree Traversal
        • Breadth First Search or BFS for a Graph
        • BFS for Disconnected Graph
      • Trees and Tree Algorithms
      • Graph and its representations
      • Graph Data Structure Interview Questions
      • Graphs in Python
      • GitHub Repo's
    • Python in CG Production
    • GLSL/HLSL Shading programming
    • Deep Learning Specialization
      • Neural Networks and Deep Learning
      • Untitled
      • Untitled
      • Untitled
    • TensorFlow for AI, ML, and DL
      • Google ML Crash Course
      • TensorFlow C++ API
      • TensorFlow - coursera
      • Notes
      • An Introduction to different Types of Convolutions in Deep Learning
      • One by One [ 1 x 1 ] Convolution - counter-intuitively useful
      • SqueezeNet
      • Deep Compression
      • An Overview of ResNet and its Variants
      • Introducing capsule networks
      • What is a CapsNet or Capsule Network?
      • Xception
      • TensorFlow Eager
    • GitHub
      • Project README
    • Agile - User Stories
    • The Open-Source Data Science Masters
    • Coding Challenge Websites
    • Coding Interview
      • leetcode python
      • Data Structures
        • Arrays
        • Linked List
        • Hash Tables
        • Trees: Basic
        • Heaps, Stacks, Queues
        • Graphs
          • Shortest Path
      • Sorting & Searching
        • Depth-First Search & Breadth-First Search
        • Backtracking
        • Sorting
      • Dynamic Programming
        • Dynamic Programming: Basic
        • Dynamic Programming: Advanced
    • spaCy
    • Pandas
    • Python Packages
    • Julia
      • jupyter
    • macos
    • CPP
      • Debugging
      • Overview of memory management problems
      • What are lvalues and rvalues?
      • The Rule of Five
      • Concurrency
      • Avoiding Data Races
      • Mutex
      • The Monitor Object Pattern
      • Lambdas
      • Maya C++ API Programming Tips
      • How can I read and parse CSV files in C++?
      • Cpp NumPy
    • Advanced Machine Learning
      • Wk 1
      • Untitled
      • Untitled
      • Untitled
      • Untitled
  • data science
    • Resources
    • Tensorflow C++
    • Computerphile
      • Big Data
    • Google ML Crash Course
    • Kaggle
      • Data Versioning
      • The Basics of Rest APIs
      • How to Make an API
      • How to deploying your API
    • Jupiter Notebook Tips & Tricks
      • Jupyter
    • Image Datasets Notes
    • DS Cheatsheets
      • Websites & Blogs
      • Q&A
      • Strata
      • Data Visualisation
      • Matplotlib etc
      • Keras
      • Spark
      • Probability
      • Machine Learning
        • Fast Computation of AUC-ROC score
    • Data Visualisation
    • fast.ai
      • deep learning
      • How to work with Jupyter Notebook on a remote machine (Linux)
      • Up and Running With Fast.ai and Docker
      • AWS
    • Data Scientist
    • ML for Beginners (Video)
    • ML Mastery
      • Machine Learning Algorithms
      • Deep Learning With Python
    • Linear algebra cheat sheet for deep learning
    • DL_ML_Resources
    • Awesome Machine Learning
    • web scraping
    • SQL Style Guide
    • SQL - Tips & Tricks
  • 💡Ideas & Thoughts
    • Outdoors
    • Blog
      • markdown
      • How to survive your first day as an On-set VFX Supervisor
    • Book Recommendations by Demi Lee
  • career
    • Skills
    • learn.co
      • SQL
      • Distribution
      • Hypothesis Testing Glossary
      • Hypothesis Tests
      • Hypothesis & AB Testing
      • Combinatorics Continued and Maximum Likelihood Estimation
      • Bayesian Classification
      • Resampling and Monte Carlo Simulation
      • Extensions To Linear Models
      • Time Series
      • Distance Metrics
      • Graph Theory
      • Logistic Regression
      • MLE (Maximum Likelihood Estimation)
      • Gradient Descent
      • Decision Trees
      • Ensemble Methods
      • Spark
      • Machine Learning
      • Deep Learning
        • Backpropagation - math notation
        • PRACTICE DATASETS
        • Big Data
      • Deep Learning Resources
      • DL Datasets
      • DL Tutorials
      • Keras
      • Word2Vec
        • Word2Vec Tutorial Part 1 - The Skip-Gram Model
        • Word2Vec Tutorial Part 2 - Negative Sampling
        • An Intuitive Explanation of Convolutional Neural Networks
      • Mod 4 Project
        • Presentation
      • Mod 5 Project
      • Capstone Project Notes
        • Streaming large training and test files into Tensorflow's DNNClassifier
    • Carrier Prep
      • The Job Search
        • Building a Strong Job Search Foundation
        • Key Traits of Successful Job Seekers
        • Your Job Search Mindset
        • Confidence
        • Job Search Action Plan
        • CSC Weekly Activity
        • Managing Your Job Search
      • Your Online Presence
        • GitHub
      • Building Your Resume
        • Writing Your Resume Summary
        • Technical Experience
      • Effective Networking
        • 30 Second Elevator Pitch
        • Leveraging Your Network
        • Building an Online Network
        • Linkedin For Research And Networking
        • Building An In-Person Network
        • Opening The Line Of Communication
      • Applying to Jobs
        • Applying To Jobs Online
        • Cover Letters
      • Interviewing
        • Networking Coffees vs Formal Interviews
        • The Coffee Meeting/ Informational Interview
        • Communicating With Recruiters And HR Professional
        • Research Before an Interview
        • Preparing Questions for Interviews
        • Phone And Video/Virtual Interviews
        • Cultural/HR Interview Questions
        • The Salary Question
        • Talking About Apps/Projects You Built
        • Sending Thank You's After an Interview
      • Technical Interviewing
        • Technical Interviewing Formats
        • Code Challenge Best Practices
        • Technical Interviewing Resources
      • Communication
        • Following Up
        • When You Haven't Heard From an Employer
      • Job Offers
        • Approaching Salary Negotiations
      • Staying Current in the Tech Industry
      • Module 6 Post Work
      • Interview Prep
  • projects
    • Text Classification
    • TERRA-REF
    • saildrone
  • Computer Graphics
  • AI/ML
  • 3deeplearning
    • Fast and Deep Deformation Approximations
    • Compress and Denoise MoCap with Autoencoders
    • ‘Fast and Deep Deformation Approximations’ Implementation
    • Running a NeuralNet live in Maya in a Python DG Node
    • Implement a Substance like Normal Map Generator with a Convolutional Network
    • Deploying Neural Nets to the Maya C++ API
  • Tools/Plugins
  • AR/VR
  • Game Engine
  • Rigging
    • Deformer Ideas
    • Research
    • brave rabbit
    • Useful Rigging Links
  • Maya
    • Optimizing Node Graph for Parallel Evaluation
  • Houdini
    • Stuff
    • Popular Built-in VEX Attributes (Global Variables)
Powered by GitBook
On this page
  • Dijkstra’s algorithm
  • Simple array implementation
  • Binary heap implementation
  • The Bellman-Ford algorithm
  • The Floyd-Warshall algorithm
  1. coding
  2. Coding Interview
  3. Data Structures
  4. Graphs

Shortest Path

Dijkstra’s algorithm

Procedure DIJKSTRA(G, s) 

Inputs: 
    * G: a directed graph containing a set V of n vertices and a set E of m 
        directed edges with nonnegative weights. 
    * s: a source vertex in V. 
    
Result: For each non-source vertex v in V, shortest[v] is the weight sp(s, v) 
        of a shortest path from s to v and pred[v] is the vertex preceding v 
        on some shortest path. For the source vertex s, shortest[s] = 0 and 
        pred[s] = NULL. If there is no path from s to v, then shortest[v] = ∞ 
        and pred[v] = NULL. 
        
1. Set shortest[v] to ∞ for each vertex v except s, set shortest[s] to 0, 
        and set pred[v] to NULL for each vertex v. 
2. Set Q to contain all vertices.
3. While Q is not empty, do the following:  
        A. Find the vertex u in set Q with the lowest shortest value and 
                remove it from Q. 
        B. For each vertex v adjacent to u:  
                i. Call RELAX(u, v).
Procedure RELAX(u, v) 
    Inputs: u, v: vertices such that there is an edge (u, v). 
    Result: The value of shortest[v] might decrease, and if it does, 
            then pred[v] becomes u. 
        
    1. If shortest[u] + weight(u, v) < shortest[v], 
            then set shortest[v] to shortest[u] + weight(u, v) 
            and set pred[v] to u.
def graph_distance(g: object, s: object) -> object:
    '''
    Dijkstra Algorithm -> find the shortest path between two vertices
    :param g: a square matrix
    :param s: start index
    :return: shortest path
    '''
    n = len(g)
    distances = [float('Inf')] * n
    queue = set(range(n))

    # initial node has a distance of 0
    distances[s] = 0

    while len(queue):
        # find the element with min distance
        min_index = -1
        for i in queue:
            if min_index == -1 or distances[i] < distances[min_index]:
                min_index = i

        # remove min_index from the queue
        queue.remove(min_index)

        # look at all of the unvisited neighbours
        for next_index in range(n):
            weight = g[min_index][next_index]
            if weight != -1:
                # re-assess distance
                other_dist = distances[min_index] + weight

                if other_dist < distances[next_index]:
                    distances[next_index] = other_dist

    return distances


g = [[-1,  3,  2],
     [ 2, -1,  0],
     [-1,  0, -1]]
s = 0
print(graph_distance(g, s))  # [0, 2, 2]

Simple array implementation

Procedure DIJKSTRA(G, s) 
Inputs and Result: Same as before. 
    1. Set shortest[v] to ∞ for each vertex v except s, set shortest[s] to 0, 
        and set pred[v] to NULL for each vertex v.

    2. Make Q an empty priority-queue. 
    3. For each vertex v:  
        A. Call INSERT(Q, v). 
    4. While Q is not empty, do the following:  
        A. Call EXTRACT-MIN(Q) and set u to hold the returned vertex. 
        B. For each vertex v adjacent to u:  
            i. Call RELAX(u, v). 
            ii. If the call to RELAX(u, v) decreased the value of shortest[v], 
                then call DECREASE-KEY(Q, v).

Operations:

  • INSERT (Q, v) inserts vertex v into set Q. (Dijkstra’s algorithm calls INSERT n times.)

  • EXTRACT-MIN (Q) removes the vertex in Q with the minimum shortest value and returns this vertex to its caller. (Dijkstra’s algorithm calls EXTRACT-MIN n times.)

  • DECREASE-KEY (Q, v) performs whatever bookkeeping is necessary in Q to record that shortest[v] was decreased by a call of RELAX. (Dijkstra’s algorithm calls DECREASE-KEY up to m times.)

Binary heap implementation

A binary heap organizes data as a binary tree stored in an array. A binary tree is a type of graph, but we refer to its vertices as nodes, the edges are undirected, and each node has 0, 1, or 2 nodes below it, which are its children. On the left side of the figure on the next page is an example of a binary tree, with the nodes numbered. Nodes with no children, such as nodes 6 through 10, are leaves.

A binary heap is a binary tree with three additional properties. First, the tree is completely filled on all levels, except possibly the lowest, which is filled from the left up to a point. Second, each node contains a key, shown inside each node in the figure. Third, the keys obey the heap property: the key of each node is less than or equal to the keys of its children. The binary tree in the figure is also a binary heap.

Procedure HEAPSORT(A, n) 

Inputs: 
    * A: an array. 
    * n: the number of elements in A to sort. 
    
Output: An array B containing the elements of A, sorted. 

1. Build a binary heap Q from the elements of A. 
2. Let B[1 . . n] be a new array. 
3. For i = 1 to n:  
    A. Call EXTRACT-MIN(Q) and set B[i] to the value returned. 
4. Return the B array.

The Bellman-Ford algorithm

Procedure BELLMAN-FORD(G, s)

Inputs:
    * G: a directed graph containing a set V of n vertices and 
            a set E of m directed edges with arbitrary weights. 
    * s: a source vertex in V. 
    
Result: Same as DIJKSTRA. 
1. Set shortest[v] to ∞ for each vertex v except s, set shortest[s] to 0, 
    and set pred[v] to NULL for each vertex v. 
2. For i = 1 to n − 1:  
    A. For each edge (u, v) in E:  
        i. Call RELAX(u, v).
Procedure FIND-NEGATIVE-WEIGHT-CYCLE(G) 

Input: 
    G: a directed graph containing a set V of n vertices and 
        a set E of m directed edges with arbitrary weights on 
        which the BELLMAN-FORD procedure has already been run. 
        
Output: Either a list of vertices in a negative-weight cycle, in order, 
        or an empty list if the graph has no negative-weight cycles. 
        
1. Go through all edges to find any edge (u, v) such that 
    shortest[u] + weight(u, v) < shortest[v]. 
2. If no such edge exists, then return an empty list. 
3. Otherwise (there is some edge (u, v) for which 
    shortest[u] + weight(u, v) < shortest[v]), do the following:  
    A. Let visited be a new array with one element for each vertex. 
        Set all elements of visited to FALSE. 
    B. Set x to v. 
    C. While visited[x] is FALSE, do the following:  
        i. Set visited[x] to TRUE. 
        ii. Set x to pred[x] 
    D. At this point, we know that x is a vertex on a negative-weight cycle. 
        Set v to pred[x]. 
    E. Create a list cycle of vertices initially containing just x. 
    F. While v is not x, do the following:  
        i. Insert vertex v at the beginning of cycle. 
        ii. Set v to pred[v]. 
    G. Return cycle.

The Floyd-Warshall algorithm

Now suppose that you want to find a shortest path from every vertex to every vertex. That’s the all-pairs shortest-paths problem.

The classic example of all-pairs shortest paths—which I have seen several authors refer to—is the table that you see in a road atlas giving distances between several cities. You find the row for one city, you find the column for the other city, and the distance between them lies at the intersection of the row and column.

Procedure FLOYD-WARSHALL(G) 

Input: G: a graph represented by a weighted adjacency matrix W with n rows and 
    n columns (one row and one column per vertex). The entry in row u and 
    column v, denoted wuv, is the weight of edge (u, v) if this edge is present 
    in G, and it is ∞ otherwise. 

Output: For each pair of vertices u and v, the value of shortest[u, v, n] 
    contains the weight of a shortest path from u to v, and pred[u, v, n] 
    is the predecessor vertex of v on a shortest path from u. 
    
1. Let shortest and pred be new n × n × (n + 1) arrays. 
2. For each u and v from 1 to n:  
    A. Set shortest[u, v, 0] to wuv. 
    B. If (u, v) is an edge in G, then set pred[u, v, 0] to u. 
        Otherwise, set pred[u, v, 0] to NULL. 
3. For x = 1 to n:  
    A. For u = 1 to n:  
        i. For v = 1 to n:  
            a. If shortest[u, v, x] < shortest[u, x, x − 1] + 
                shortest[x, v, x − 1], then set shortest[u, v, x] to 
                shortest[u, x, x − 1] + shortest[x, v, x − 1] and set 
                pred[u, v, x] to pred[x, v, x − 1]. 
            b. Otherwise, set shortest[u, v, x] to shortest[u, v, x − 1] and set 
                pred[u, v, x] to pred[u, v, x − 1].
4. Return the shortest and pred arrays.

PreviousGraphsNextSorting & Searching

Last updated 6 years ago

We can store a binary heap in an array, as shown on the right in the figure. Because of the heap property, the node with the minimum key must always be at position 1. The children of the node at position i are at positions 2i2i2i and 2i+12i + 12i+1, and the node above the node at position i—its parent—is at position ⌊i/2⌋\lfloor i / 2 \rfloor ⌊i/2⌋. It is easy to navigate up and down within a binary heap when we store it in an array.

👨‍💻