Single-Source Shortest Path and Connected Components

By: Katana Graph

May 16, 2022

Single-Source Shortest Path and Connected Components

This article is the second in a series of short pieces introducing the Katana Graph Python Library for Graph Analytics. We will focus on single-source shortest path and connected components graph analytics algorithms in the library.

Single-source shortest path

Single-source shortest path (SSSP) is similar to breadth-first search, which we covered in part one of this series, but when calculating distances from a given node to all the others in a graph, SSSP takes values assigned to each edge, known as edge weights, into account. Edge weights are positive values that can represent distance, cost, or any other quantity that you wish to minimize as it accumulates along the path. This algorithm returns, for each node, its distance from the source node in which the paths are the least expensive routes between the corresponding nodes in the original graph. This is useful for route mapping, network routing, and logistics research.

There are a number of single-source shortest path algorithms, including Bellman-Ford and Dijkstra’s, that are useful in different applications or with different types of graphs. The Bellman-Ford algorithm has a greater time complexity than Dijkstra’s and is useful for small- and medium-sized graphs and is able to detect negative cycles. Dijkstra’s algorithm, on the other hand, has a logarithmic time complexity which is efficient for large/medium graphs, but it cannot detect negative cycles.

Connected components

“Connected components” describes groups of nodes within the graph that are connected internally. Bridges (or cut edges, cut points) and articulation points are edges and nodes that serve as a single point of connection between components. The removal of a bridge (edge) or articulation point (node) would increase the number of connected components. For example, if you have two groups of nodes connected by a single edge, that edge is the bridge, and removing it would result in two independent groups of nodes.

Identifying the number of components in a graph is critical for understanding its structure. For example, looking at a map of states, roads, and prominent cities would show that while there may be several roads between cities, it is primarily major roadways connecting states to one another. Viewing data in this way also displays unlikely cut points, such as a small country road on the outskirts that allows travel between two small towns while incidentally connecting two states. This algorithm has been useful for very large-scale integration (VLSI) and other electronic circuit work.

To learn more about how the Katana Graph Intelligence Platform is used to solve problems, speak to a Katana Graph Intelligence Platform expert.

Get to Know Katana Graph

We thrive on testing new and diverse ideas.

Katana Graph was born of cutting-edge research and scientific rigor, and these beginnings have a powerful effect on who we are to this day. We’re devoted to problem solving, and are relentless in our pursuit of more effective and more efficient solutions to real-world challenges. Continuous improvement is the very foundation of our success.

share

Newsletter Sign Up

Subgraph Extraction

Graph mining is a growing field of study, and its use applies to many real-world applications. In.

Read More
ETL with the Katana Graph Library

ETL (extract, transform, and load) refers to the process data engineers use to pull data from.

Read More
What Is PageRank?

The PageRank algorithm uses incoming links between a graph’s nodes to rank the nodes, giving nodes.

Read More

View All Resources

Let’s Talk

Turn Your Unmanageable
Data Into Answers

Find out how Katana Graph can help provide the foundation for your future of data-driven innovation.

Contact Sales