logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
ArraysBoyer-Moore Majority Vote AlgorithmKadane’s AlgorithmTriple Reverse algorithm aka Reversal Algorithm
Cycle detectionDijkstraDisjoint Set UnionGraphTopological SortTraversal algorithmsTree Traversal
Binary HeapBinomial HeapHeap
Cycle DetectionLinked ListSorting
Finding the majority elementRotate array by K steps
Finding If Number is PrimeGCD of two numbersPerforming ExponentiationPrime NumbersRandomising Data
3. Max Consecutive OnesHoare'S Partition SchemeLomuto Partition Scheme
DequesPriority QueueQueue
The Binary Search Master GuideThe Rotated Sorted Array Master Guide
Bubble SortCounting SortInsertion SortMerge SortPigeon Hole SortQuick SortSelection Sort
Monotonic StackMonotonic StackStackReversing an ArrayStackTower of Hanoi
Binary Tree TraversalCentre of gravityDiameter of TreeShortest Path
Algorithmic Pattern/graph

Graph

1 min read
On this pageDirected Acyclic Graph
Directed Acyclic GraphDynamic programmingReferences 

# Directed Acyclic Graph

  • It is simply a directed graph which contains no cycles - it is impossible to start at one vertex, move along a sequence of arcs and end up in the same vertex

Directed Acyclic Graph

  • Every DAG has at least one Topological Ordering.

Info

# Sink Vertex

Sink vertex is the vertex which has no outbound edges.

  • A DAG has to have at least one sink vertex. If we don’t have a sink vertex then that means that every edge will have at least one outgoing vertex and since we have finite vertices in our graph then by pigeon hole principle that means that, we will be visiting one of the already visited vertices, which implies we would have a directed cycle.

Info

A directed graph with no sink vertex must have cycle.

# Dynamic programming

  • If a directed graph is acyclic, dynamic programming can be applied to it.

    We can efficiently solve the following problems concerning paths from a starting node to an ending node

    • how many different paths are there?
    • what is the shortest/longest path?
    • what is the minimum/maximum number of edges in a path?
    • which nodes certainly appear in any path?

# References

  • Directed graphs chapter from "Competitive Programmer’s Handbook"

Dijkstra’s Algorithm_ Visual Guide

←PreviousDisjoint Set UnionNext→Topological Sort

On this page

Directed Acyclic GraphDynamic programmingReferences