GRAPH PATHWAY ALGORITHMS

Silas Liu - December 07, 2024

Graph Algorithms

Graphs are versatile structures that model real-world problems involving network of interconnected elements. These structures enable the application of graph algorithms to uncover insights into relationships, optimize systems and solve complex problems in diverse fields, such as social networks, navigation, logistics and communication systems.

There are many different graph algorithms for different tasks such as clustering, community detection or shortest path computation. Pathway algorithms specialize in identifying optimal routes within a graph. Given the variety of possible scenarios, such as unweighted or weighted edges, positive or negative weights, acyclic or cyclic graphs, there are numerous pathway algorithms, each tailored to a specific setup.

Graph Algorithms are powerful tools for solving problems that involve networks of connected elements (nodes) linked by relationships (edges). There are many different algorithms that help analyze complex systems like social networks, maps or logistical pathways. Graph algorithms offer efficient solutions for various tasks from finding shortest path to detecting clusters or communities. By modelling real-world problems as graphs we can derive valuable insights and solutions related to structure and data.

Pathway Algorithms focus on identifying the most efficient routes between nodes within a graph and represent one of the most common use cases for graph analysis. Their applications cover many scenarios such as navigation, logistics or network routing. Different scenarios may require variations in setup, such as unweighted or weighted edges, non-negative or negative weights, acyclic or cyclic graphs, and the presence of negative cycles. Next, we explore some of the key algorithms in this domain.

1. Depth First Search (DFS)

The Depth First Search (DFS) is a fundamental graph traversal algorithm, used to explore nodes and edges systematically. It often serves as a building block for more complex tasks such as counting connected components, determining connectivity and identifying bridges or articulation points.

The DFS is implemented with a LIFO (Last-In, First-Out) structure, using a stack. The algorithm explores each path from a starting node until it can no longer continue, then backtracks to explore unexplored paths until all nodes are visited.

Complexity
O(V+E)

2. Breadth First Search (BFS)

The Breadth First Search (BFS) is another foundational graph traversal algorithm, used to explore nodes and edges of a graph. It is also used as a building block in other algorithms. The BFS is the best algorithm for one specific setting: finding the shortest path on unweighted graphs.

The BFS may be implemented with a FIFO (First-In, First-Out) structure, using a queue. Starting from an initial node, it explores all neighboring nodes first, before moving to their neighbors, continuing level by level until all nodes have been explored.

Complexity	Recommended Graph Size	Unweighted Edges	Weighted Edges
O(V+E)	Large	Best algorithm	Does not work

3. Dijkstra Algorithm

Dijkstra's Algorithm is the best algorithm to find the shortest path in graphs with non-negative weighted edges. This scenario can be applied to several use-cases such as:

Map routes with distance, travel time or toll cost as edge weights
Telecommunication networks with latency or bandwidth as edge weights
Logistics with fuel cost or time travel as edge weights

The algorithm finds the shortest path by maintaining a list of minimum distances from a starting node to all other nodes, updating these distances as it explores the graph. Starting from an initial node, it examines each neighboring node, updating the shortest known distance if it finds a quicker path. The algorithm uses a priority queue to select the next node to process, always choosing the one with the smallest distance so far. As it moves through the graph, it relaxes edges by continually updating distances until every node's shortest path is determined.

As an example we have a map simulating intersections and street distances. The algorithm traverses the entire graph, finds the shortest path from the first intersection to all others, and in the end, shows the shortest path to the last intersection.

Complexity	Recommended Graph Size	Weighted Edges	Non-negative weights	Negative weights
O((V+E) log V)	Large/Medium	Yes	Best algorithm	No

4. Bellman-Ford Algorithm

The Bellman-Ford algorithm is an efficient algorithm for finding the shortest path in graphs that have negative weight edges. It is a Single Source Shortest Path (SSSP) algorithm and is also capable of detecting negative cycles. This makes it especially useful in scenarios where negative weights can appear such as:

Financial arbitrage, where the algorithm can identify opportunities for profit between different markets by detecting negative cycles in currency exchange rates
Optimization problems in resource management where costs can decrease over time or with repeated actions

The algorithm works by iterating over all edges multiple times, adjusting the distances between nodes. In each iteration, it checks if a shorter path exists to each node and updates the distance accordingly. This process is repeated N-1 times, where N is the number of nodes in the graph. If after these iterations, any distance can still be reduced, it is flagged, indicating the presence of a negative cycle.

Below is an example of the Bellman-Ford algorithm. We have a graph representing exchange rates between different currencies. The algorithm's goal is to find the best conversion paths, starting from the initial node BRL. Since exchange rates are calculated by multiplying rather than adding, we represent the conversion rates as logarithmic values, so the algorithm can work with sums.

Complexity	Recommended Graph Size	Weighted Edges	Negative Weights	Detect Negative Cycles
O(VE)	Medium/Small	Yes	Yes	Yes

In the following animation, we first see Step 1 through Step 6, showing each relaxation step as the shortest paths are updated, highlighted in red, from each node. Then, each iteration from 1 to 5 shows paths that lead to shorter paths, again highlighted in red. In this graph we can see a negative cycle, which causes the minimum path values to keep decreasing with each iteration. Finally we have the negative cycle detection steps, marking these nodes with a distance of -infinite. The nodes with minimum distances are shown in green, while the nodes involved in negative cycles are shown in red.

The final solution shows that the best conversion rates are as follows:

USD: BRL->USD: 100 BRL becomes 20 USD through direct conversion
EUR: BRL->USD->EUR: 100 BRL becomes 18.8 EUR by going through USD. If converted directly, 100 BRL would result in 16.7 EUR
There is an arbitrage cycle along the path GBP->HUF->PLN->GBP: If we multiply all exchange rates starting from GBP, we get a multiplier of 1.34. This means that 100 GBP would result in 134.19 GBP after one cycle, meaning that the cycle yields more money than the initial amount.

5. Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a classic approach for finding the shortest paths for all pairs of nodes in a weighted graph. Known as an All-Pairs Shortest Path (APSP) algorithm, Floyd-Warshall is effective for smaller graphs or specific applications but is often less efficient for large graphs compared to other algorithms due to its higher computational complexity. Despite this, it remains valuable for certain use cases, such as:

Logistics and Route Optimization: calculates shortest paths across all origin-destination pairs in large transport or delivery networks for cost-effective routing
Communication Network Analysis: identify optimal data transfer paths between devices by minimizing latency across all device pairs

The Floyd-Warshall algorithm represents the graph using an adjacency matrix, containing the distance from all nodes to all nodes. The core idea of the algorithm is to iteratively improve this matrix by considering each node as intermediate nodes and gradually building up all possible paths between each pair of nodes. By the end the matrix contains the shortest paths between every pair of nodes. Then the algorithm runs again, to flag negative cycles.

As an example we have here a logistic system for postal deliveries. The blue points represent neighborhoods and the red points represent the Postal Distribution Centers.

Complexity	Recommended Graph Size	Weighted Edges	Negative Weights	Detect Negative Cycles
O(V^3)	Small	Yes	Yes	Yes

Using the Floyd-Warshall algorithm, it is possible to determine the shortest path between all points. In our problem, we are particularly interested in identifying the closest Distribution Center to each neighborhood. This problem was simplified to use geodetic distances, but it could also consider route distances and intermediate postal units.

6. Directed Acyclic Graphs (DAG) Shortest Path

A Directed Acyclic Graph (DAG) is a graph with directed edges and no cycles, meaning it is impossible to return to the same node by following a path. DAGs can have weighted or unweighted edges, and weights may be positive or negative. They are widely used to model dependencies or hierarchical processes, making them suitable for scenarios where tasks must follow a specific order. There are many use cases, such as:

Resolving file dependencies in build systems or compilers
Representing data flow in neural networks or distributed computing
Modeling version control systems like Git or genealogical trees
Genetic sequencing, where DAGs capture interactions between genes

The shortest path on DAGs can be efficiently found by leveraging its acyclic nature. The algorithm has two main steps:

Topological Sort: Nodes are reordered so that every prerequisite task comes before dependent tasks. This is achieved using DFS, adding nodes to the order during the return step of recursion
Shortest Path Finding: Using the topological order, the algorithm processes nodes sequentially, relaxing distances to their neighbors and updating the shortest path efficiently

Below we have an example illustrating the two steps of finding the shortest path in a DAG. First, we determine the topological order, represented by the numbers on the nodes. Next, we highlight the shortest paths from node 0 to all other nodes in red.

Complexity	Directed Edges	Cycles	Positive Weights	Negative Weights
O(V+E)	Yes	No	Yes	Yes