DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workkloads.

Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Solving Three Medium-Level Coding
  • Universal Implementation of BFS, DFS, Dijkstra, and A-Star Algorithms
  • Predicting Ad Viewability With XGBoost Regressor Algorithm
  • Graph API for Entra ID (Azure AD) Object Management

Trending

  • A Developer's Guide to Mastering Agentic AI: From Theory to Practice
  • Java Virtual Threads and Scaling
  • GDPR Compliance With .NET: Securing Data the Right Way
  • Internal Developer Portals: Modern DevOps's Missing Piece
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Algorithm of the Week: Shortest Path in a Directed Acyclic Graph

Algorithm of the Week: Shortest Path in a Directed Acyclic Graph

By 
Stoimen Popov user avatar
Stoimen Popov
·
Oct. 30, 12 · Interview
Likes (0)
Comment
Save
Tweet
Share
28.0K Views

Join the DZone community and get the full member experience.

Join For Free

Introduction

We saw how to find the shortest path in a graph with positive edges using the Dijkstra’s algorithm. We also know how to find the shortest paths from a given source node to all other nodes even when there are negative edges using the Bellman-Ford algorithm. Now we’ll see that there’s a faster algorithm running in linear time that can find the shortest paths from a given source node to all other reachable vertices in a directed acyclic graph, also known as a DAG.

Because the DAG is acyclic we don’t have to worry about negative cycles. As we already know it’s pointless to speak about shortest path in the presence of negative cycles because we can “loop” over these cycles and practically our path will become shorter and shorter.

Negative Cycles

The presence of a negative cycles make our attempt to find the shortest path pointless!

Thus we have two problems to overcome with Dijkstra and the Bellman-Ford algorithms. First of all we needed only positive weights and on the second place we didn’t want cycles. Well, we can handle both cases in this algorithm.

Overview

The first thing we know about DAGs is that they can easily be topologically sorted. Topological sort can be used in many practical cases, but perhaps the mostly used one is when trying to schedule dependent tasks.

Topological Sort

Topological sort is often used to “sort” dependent tasks!

After a topological sort we end with a list of vertices of the DAG and we’re sure that if there’s an edge (u, v), u will precede v in the topologically sorted list.

Topological Sort (part 2)

If there’s an edge (u,v) then u must precede v. This results in the more general case from the image. There’s no edge between B and D, but B precedes D!

This information is precious and the only thing we need to do is to pass through this sorted list and to calculate distances for a shortest paths just like the algorithm of Dijkstra.

OK, so let’s summarize this algorithm:
- First we must topologically sort the DAG;
- As a second step we set the distance to the source to 0 and infinity to all other vertices;
- Then for each vertex from the list we pass through all its neighbors and we check for shortest path;

It’s pretty much like the Dijkstra’s algorithm with the main difference that we used a priority queue then, while this time we use the list from the topological sort.

Code

This time the code is actually a pseudocode. Although all the examples so far was in PHP, perhaps pseudocode is easier to understand and doesn’t bind you in a specific language implementation. Also if you don’t feel comfortable with the given programming language it can be more difficult for you to understand the code than by reading pseudocode.

1. Topologically sort G into L;
2. Set the distance to the source to 0;
3. Set the distances to all other vertices to infinity;
4. For each vertex u in L
5.    - Walk through all neighbors v of u;
6.    - If dist(v) > dist(u) + w(u, v) 
7.       - Set dist(v) <- dist(u) + w(u, v);

Application

It’s clear why and where we must use this algorithm. The only problem is that we must be sure that the graph doesn’t have cycles. However if we’re aware of how the graph is created we may have some additional information if there are cycles or not – then this linear time algorithm can be very applicable.

 

 

 

Algorithm Graph (Unix) Directed acyclic graph

Published at DZone with permission of Stoimen Popov, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Solving Three Medium-Level Coding
  • Universal Implementation of BFS, DFS, Dijkstra, and A-Star Algorithms
  • Predicting Ad Viewability With XGBoost Regressor Algorithm
  • Graph API for Entra ID (Azure AD) Object Management

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!