The Shortest path algorithms so you go to google maps and you want to find the shortest path from one city to another.  Two algorithms can help you, they both calculate the shortest distance from a source node into all other nodes, one node can handle negative weights with cycles and another cannot, Dijkstra cannot and bellman ford can.

One is Dijkstra if you run the Dijkstra algorithm on this map its input would be a single source node and its output would be the path to all other vertices.  However, there is a caveat if Elon mask comes and with some magic creates a black hole loop which makes one of the edges negative weight then the Dijkstra algorithm would fail to give you the answer.

This is where bellman Ford algorithm comes into place, it's like the Dijkstra algorithm only it knows to handle well negative weight in edges.

Dijkstra has an issue handling negative weights and cycles

Bellman's ford algorithm target is to find the shortest path from a single node in a graph to all other nodes.

When we discussed Dijkstra's algorithm we saw that it's moving forward and it's quite efficient with a heap it's only O(E+V) * O(VlgV) however if the graph is having negative edge weights then Dijkstra's algorithm does not take care of it, it would simply fail Dijkstra algorithm is simply not intended for graphs with negative edge weights.  The reason for the above time complexity is that the Dijkstra's algorithm simply scan's the graph in a rather BFS way it's not a strict BFS there are rules to which vertices to visit next but it's like swooping the graph from your source node into all other nodes the reason for the O(VlgV) is that when it chooses which next node to choose then we use a heap sort to find the one currently having the minimal weight.

To recap here are the steps for Dijkstra algorithm are:
  1. Initialize distances to infinity.
  2. Pick first node and calculate distances to adjacent nodes.
  3. Pick next node with minimal distance; repeat adjacent node distance calculations.
  4. Final result of shortest-path tree.

So as Bellman's ford algorithm can handle negative edges it can also detect negative cycles.  Why would we need to detect negative cycle? in arbitrage trading we can find we could make money of thin air by selling on one stock exchange high and buying on another low, this is a negative cycle because we can continue this cycle take the money we made on the high stock exchange and with the negative edge buy on a lower price on the lower priced stock exchange.

Of course if we find out that our graph contains a negative cycle to a target node this means there would be no shortest path to this target node or it would be minus infinity.

So while the bellman ford algorithm can handle negative weighted graphs while the Dijkstra's cannot nothing in life comes for free and bellman ford is slower than Dijkstra's algorithm after all it's making fewer assumptions about the weights they should not all be non-negative.

When we have a negative weights its possible for a negative to exist and then Dijkstra algorithm would find better and better paths.

What would a negative infinity mean to us, it depends on our problem it can be a good thing to have negative infinity path but it could also mean to have a bad thing to have a negative infinity path.

Before we get to the actual Bellman ford algorithm let's reap the terms we have for graphs

E is the edges more specifically we are interested in the number of edges

A directed edge is an edge going from a source node to a target node with some weight.

V is the vertices more specifically we are interested in the number of vertices
S is the starting node
D is an array of size V that tracks the best distance from S to each node.

The distance D array first is initialized to positive infinity.

In our first step we go over array D which stores the distance the best distance from S to any node as infinity, we don't know yet of any distance, so we start with infinity.

However, we have a starting point, so we already know the distance to the starting node which means that D[S] = 0.  The path of the starting node to itself is zero.

Now we start reducing the weights of these edges, we are going to do this stay tuned:

For each edge (order does not matter) check if the edge makes the target node weight lower if so replace it with lower number, repeat this whole process for all edges V-1 Times
When we start with this process we are going to update all weights because any weight would be smaller than infinity which we initialized all weights in the shortest distance to.
  
 How do we detect negative cycles?

We run the algorithm a second time, if any node value changed then we update that node to having cost of negative infinity and that's it. When we say that we run the algorithm a second time we run again the V-1 times of edges relaxing.

At the end you return the distance array D which contains all the weights. Then if you want to know the shortest path from a node to another one you just find that target node in the distance array.

And that was bellman ford algorithm.

Posted by
1

View comments

Chapter X: Getting Started with AWS Step Functions

We've successfully navigated the world of serverless compute with AWS Lambda. You've learned how to create event-driven functions and unlock the power of code without managing servers. Now, let's elevate our serverless capabilities by delving into AWS Step Functions, a service that allows you to coordinate multiple AWS services into serverless workflows so you can build and run sophisticated applications.

Think of Step Functions as the conductor of your serverless orchestra. While Lambda functions are the individual instruments performing specific tasks, Step Functions defines the order in which these instruments play, ensuring a harmonious and well-structured performance.

Introduction

Tools that enhance productivity and streamline workflows are in high demand. Among these, AI-powered coding assistants have taken center stage, promising to act as virtual pair programmers. While GitHub Copilot and JetBrains AI Assistant have become household names in this space, a lesser-known but intriguing contender, Aider, is making waves.

Introduction

The line between batch and streaming processing is blurring. Apache Iceberg, an open table format, is at the forefront of this shift, promising to unify these paradigms in a single, scalable framework. But how does it achieve this? Can it replace traditional streaming systems like Kafka? And how do tools like Flink and Spark Streaming leverage Iceberg for streaming workloads? Let’s dive in.

502 Bad Gateway Errors with Reflex Python Behind NGINX

Overview

You're experiencing a 502 Bad Gateway error every few hours with your Reflex Python application behind NGINX, which gets resolved by restarting the app but recurs later. This suggests the problem lies with the Reflex app or its connection to NGINX.

Likely Cause

It seems likely that the Reflex Python application is becoming unresponsive after a few hours, possibly due to memory leaks, resource exhaustion, or unhandled exceptions.

Overview

RDS with PostgreSQL is cost-effective for general-purpose databases, while Redshift seems more economical for large-scale data analytics due to lower storage costs.Matching use cases are using RDS for transactional applications and Redshift for analytical queries on big datasets, with costs varying by workload.An unexpected detail is that Redshift's compute costs per hour can be higher, but its storage is significantly cheaper, affecting total cost based on data size.Pricing Comparison

Web Scraping

- https://www.scrapingdog.com/

Is common for ClickHouse to use S3 for data storage. And while it's not as common (yet) for ClickHouse to directly integrate with Iceberg as a table format, the integration is evolving and becoming increasingly relevant in modern data architectures.

Let's break down each part:

1. ClickHouse and S3 (Common and Yes):

Yes, it's very common for ClickHouse to interact with and utilize S3. In cloud deployments, especially on AWS (where S3 is native), it's a highly prevalent pattern.

Unraveling Flux: Why Your React Frontend Needs a Data Flow Blueprint

Hey Back-End Engineers, let's talk about frontends. Specifically, React frontends, which you've likely heard a lot about. You might be thinking, "Frontend? Isn't that just HTML, CSS, and a bit of JavaScript glue? We handle the real data logic on the server."  Well, in today's web applications, that "bit of JavaScript glue" is doing a lot more, and that's where things like Flux come in.

Imagine your backend system.

In today's data-driven world, operational metrics are the lifeblood of any organization running complex systems. They provide crucial insights into performance, availability, and user behavior. However, as systems become more intricate and user bases grow, we often encounter the daunting challenge of high cardinality metrics. Imagine tracking metrics not just by server, but by individual container, user session, product SKU, or geographical location.

Document Processing Pipelines vs. Kubernetes Containers: A Comparative Analysis with Orchestration Insights

When designing a document processing system, architects and engineers must choose between managed document processing pipelines (e.g., AWS Glue, Google Dataflow) and Kubernetes (k8s)-based containerized solutions.
Popular Posts
Popular Posts
Contributors
Contributors
Archive
Archive
Labels
Labels
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.