Graph algorithms allow us to process complex relational data. These can determine the shortest route between destinations, discover relationships in social networks, and aid navigation throughout webpages. Algorithms operate on graph data structures, consisting of nodes (vertices) and connections between nodes (edges). There are many graph algorithms to choose from depending on the type of connections and desired analysis.
Some important types of graph algorithms include Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra’s Algorithm and the Bellman-Ford Algorithm. Knowing which to use in given scenarios can be very advantageous to solving problems in fields such as networks, transport, programming and data analysis. Finding out more about Graph Algorithms allows students and developers to better understand how to explore, arrange and process complex relational data to give meaningful outputs.
Overview of Graphs
Graphs consist of vertices and edges. Vertices represent entities and edges represent relationships between entities. In a social media network, each user in the network can be represented by a vertex, and relationships (friendships) between users can be represented by edges. Graphs can be directed where movement along edges is one way, or undirected where movement along edges can be both ways.
Graphs can also be weighted so that numbers can be assigned to each edge to represent distance, cost and time, or unweighted so that all connections are assumed to be equal. Depending on the type of graph, different algorithms will be more suitable to solve problems in the graph in an efficient way.
Representing Graphs
Graphs can be represented in two common formats within computers. Adjacency Lists and Adjacency Matrices. In adjacency lists, every vertex has a list of connected vertices. This representation of graphs is efficient in terms of memory usage in sparse graphs where there are few connections between nodes. Adjacency matrices use 2-D arrays to show connections between all pairs of vertices. A value is given in each position to indicate if there is a connection between two vertices, and possibly give the weight of the edge.
While adjacency matrices can take up quite a huge amount of memory in graphs with many vertices but few connections, adjacency matrices are efficient in determining if a given connection exists. Depending on the size of the graph, the density of connections and the type of operations required in the application, an adjacency list or matrix may be the best representation.
1. Breadth-First Search (BFS)
Breadth-First Search (BFS) is a graph traversal algorithm. Vertices are searched in a breadth-wise manner. This means that all of the immediate connections to the starting node are considered before searching further connections. BFS uses a queue data structure. A queue follows a First In First Out (FIFO) approach. Therefore, the vertex which was added to the queue first will be the first to be removed and searched.
The algorithm begins by choosing a start vertex. This vertex is marked as visited, and is placed in the queue. The algorithm proceeds to dequeue a vertex, check for unvisited adjacent vertices, and enqueue those vertices. This continues until all reachable vertices are visited, or the desired vertex is found.
How the Algorithm Works
Within social media, if a person (A) has 3 connections (B, C and D), and each of these connections have further connections, BFS can be used to find all people in a given number of connections. Within BFS, we first look at all of the immediate connections of person A. Then we look at all of the connections of these people, before going further.
For example, if person A is connected to persons B and C, and person B is connected to persons D and E, the algorithm will search in the order A, B and C, before searching D and E. A set of visited vertices are kept to prevent processing the same vertex multiple times, since there may be multiple pathways leading to the same person in a network.

Applications
BFS can be very useful within various applications. For example, it can be used within transport systems to find the minimal number of connections (roads/changes) between 2 locations, assuming that all connections have equal costs. It can also be used within web scraping applications, to find web pages. Starting from a web page, the links can be followed, and the new web pages found can be searched in the next level of connections.
Within computer networks, BFS can be used to search devices within a network to see if certain nodes can be reached. Within social media applications, BFS can be used to recommend people to users based on shared connections, or to find users within a certain distance of connections. As a result, BFS can be very useful to process relational data in an ordered fashion, without searching far away nodes before nearer nodes.
Efficiency
The efficiency of an algorithm can be defined by its time and space complexity. Using adjacency lists, the time complexity of BFS is O(V+E) since every reachable vertex and its edges are checked. The space complexity of this algorithm is also O(V) as vertices may have to be stored within the queue and set of visited vertices.
BFS is very efficient within large graphs, as long as connections can be efficiently accessed. However, storing many vertices can increase the memory requirements of the algorithm. Despite this, BFS is often a good choice for finding the shortest path in unweighted graphs, or if vertices need to be searched level by level.
2. Depth-First Search (DFS)
Depth-First Search (DFS) is another important graph traversal algorithm. Unlike BFS, which searches level by level, DFS will follow one connection as far as possible, before backtracking and searching other connections. DFS can be implemented via stacks, or recursively. Stacks follow a Last In First Out (LIFO) approach, meaning that the last item to be added to a stack is the first item to be processed.
The algorithm begins by selecting a start vertex. This vertex is marked as visited, and an unvisited adjacent vertex is moved to. The algorithm proceeds to follow as many connections as possible. Once no unvisited vertices can be found from a given vertex, the algorithm will backtrack to look for other connections. This continues until all reachable vertices have been checked.
How the Algorithm Works
Imagine a program is trying to find the shortest path through a maze. The program will enter the maze from the start, and go down one of the available paths. It will continue through until it reaches its dead-end or a section that it has already visited. At this point, it will backtrack through the maze until it reaches a junction, and go down an unvisited path.
This is a representation of a DFS algorithm. In a graph where A is connected to B and C, B is connected to D and E, DFS may search A, B, D, E, and C (depending on the order of the connections). The order of traversal may change depending on the arrangement of connections. To prevent the search revisiting a vertex multiple times in graphs with cycles or multiple connections, a set of visited vertices is maintained.

Applications
DFS is very popular in computing. Web scraping applications can use a depth First Search to go as deep as possible into a webpage’s links, before moving onto other links. In programming, DFS can be used to solve mazes, analyse directory trees in files and search for possible pathways in interlinked systems. It can also be used to find cycles within graphs, in cases where you want to know if a path leads to a previously visited vertex.
Lastly, dependency analysis can be performed with DFS. For example, in software development, a build system may use DFS to look at the relationships between files, libraries and components. This can determine what dependencies need to be processed first. This makes DFS very useful to thoroughly search interlinked structures, especially where you may not want to prioritise nearby nodes.
Efficiency
Like BFS, the time complexity when using adjacency lists is O(V+E). All reachable vertices are checked, along with the edges. The space complexity is O(V), for the visited set and stack. However, if using a recursive method, the call stack may increase in size depending on how far into the graph the algorithm goes. Compared to BFS, DFS can be very efficient in terms of memory in some graphs, since a queue may not be required to hold large amounts of adjacent vertices at once.
However, the memory requirements will depend on the graph structure and depth of traversal. If processing extremely deep graphs, programmers may wish to avoid recursion due to limits in recursion depth. An iterative algorithm with an explicit stack may be better suited to large applications.
3. Dijkstra’s Algorithm
Dijkstra’s algorithm can be used to find the shortest path from a starting vertex to other reachable vertices in a weighted graph. Unlike BFS, edge weights are taken into account. These weights may represent distance, time, cost or anything else numerical. Initially, the algorithm assigns each vertex in the graph a distance. The starting vertex will be given a distance of 0, and all other vertices will be given a distance of infinity as their shortest distances are unknown.
From here, the vertex in the graph with the smallest distance and not yet processed is chosen. The algorithm then checks all adjacent vertices, and if a shorter distance can be found to get to that vertex, the distance will be updated. This process is known as relaxation. This process is repeated until the relevant vertices have been processed and have their shortest distances.
How the Algorithm Works
If a delivery company wants to find the shortest route between several locations, each location can be represented as a vertex, and the roads connecting them can be weighted edges. Suppose the distance between A to B is 4, A to C is 2 and C to B is 1.
While there is a direct connection between A and B, the path through C is shorter (distance = 3). Dijkstra’s algorithm can identify this by comparing distances. If a cheaper distance can be determined, then the shortest distance is updated. A priority queue is commonly used to efficiently find the vertex with the smallest tentative distance. This makes it suitable for finding optimal routes in graphs with non-negative weighted edges.

Applications
Dijkstra’s algorithm is very useful in systems where connections can have varying costs. Mapping systems can use shortest paths to give efficient routes between locations. However, real navigation systems may use a combination of several algorithms and extra information on traffic. Similarly, routing protocols in networks can use shortest paths to find efficient ways to transfer information between devices.
Delivery companies can use weighted graphs to compare distances travelled (or estimated costs) to plan efficient delivery routes. In video games and simulation software, similar techniques may be used to allow characters to navigate through virtual environments and avoid unnecessarily expensive paths. Therefore, Dijkstra’s algorithm is very useful in systems where the cheapest route through weighted connections needs to be found.
Efficiency
Depending on the representation of the graph and data structures used, Dijkstra’s algorithm can have varying efficiencies. Using adjacency lists and binary heap priority queues, the algorithm has a time complexity of O((V+E)logV). This can be simplified to O(ElgV) for connected graphs. This is because vertices and priority queue operations are processed as edges are considered.
If using adjacency matrices and a simple algorithm to find the smallest tentative distance, the algorithm generally has a time complexity of O(V² ). The space complexity is O(V), for the distance array, priority queue and other assisting structures (excluding graph memory). It is important to note that Dijkstra’s algorithm cannot be used correctly in graphs with negative edge weights. In this case, another algorithm (such as Bellman-Ford) may be more suitable.
4. Bellman-Ford Algorithm
The Bellman-Ford algorithm can be used to find the shortest distance from a starting vertex to other vertices in a weighted graph. Like Dijkstra’s algorithm, edges have weights, however, this algorithm can also be used with negative edge weights. Negative edge weights can occur in a graph if there is a discount, profit or another instance where the cost is negative.
The algorithm repeatedly relaxes edges. Initially, the starting node is given a distance of 0 and all other vertices are given a distance of infinity. All edges are checked, and if a shorter path can be found by following that edge, the distance of the destination vertex will be updated. This process is repeated V-1 times (V being the number of vertices) to determine the shortest distance when there are no negative weight cycles that can be reached.
How the Algorithm Works
Imagine a system representing financial relationships between different points. Different transactions may have positive or negative costs, and the system may want to find the cheapest sequence of connections between two points. Rather than picking the closest unvisited vertex like Dijkstra’s algorithm does, Bellman-Ford repeatedly checks every edge in the graph.
For each edge, if following the edge from the source vertex to destination vertex gives a shorter distance than previously known (based on current distance of source vertex plus edge weight), then the distance of the destination vertex is updated. After V-1 iterations, an extra check is made. If any distances can still be improved, a negative weight cycle which can be reached must be in the graph. This means that there cannot be a finite shortest distance to vertices in that cycle.
Applications
Bellman-Ford is very useful in systems with potential negative edge weights, and to detect negative weight cycles. In financial systems, it can be used to analyse exchange rates or costs of transactions in a network. However, extra precautions and validation will be required in real financial systems. In computer networks, distance vector routing protocols utilise concepts from Bellman-Ford to decide the best routes between destinations.
Every device within a network can send information on known distances to nearby devices. As new information is received, routing decisions can be updated. The algorithm can also be useful in research, optimization problems and challenges in programming which involve weighted graphs. As it can detect negative weight cycles, it is very useful in instances where it needs to be determined whether a network has a sequence of connections which can continuously decrease the calculated cost.
Efficiency
The time complexity of Bellman-Ford is O(VE), as all edges are checked in each of the V-1 main iterations and once again to detect negative weight cycles. As a result, this algorithm may be less efficient than Dijkstra’s algorithm in many scenarios, especially if there are large numbers of edges in large graphs. However, as it can be used with negative weights, it may still be a good choice in certain applications. The space complexity of the algorithm (excluding graph memory) is O(V) due to the distance array and assisting data structures.
While Bellman-Ford may be less efficient in terms of processing time than other shortest path algorithms, it can be a reliable choice if negative weights or detecting negative weight cycles is an important requirement. Developers should be aware of these considerations when deciding which algorithm to use.
Comparison Between BFS, DFS, Dijkstra and Bellman-Ford
Breadth-First Search, Depth-First Search, Dijkstra’s Algorithm and Bellman-Ford can all be used within graphs, but each have different purposes. BFS and DFS are traversal algorithms. Dijkstra’s and Bellman-Ford are shortest-path algorithms. BFS is particularly useful for finding shortest paths in unweighted graphs. DFS is useful for exploring graph structures, finding cycles and analysing dependencies. Dijkstra’s algorithm is generally the best choice for weighted graphs with non-negative weights as it is very efficient. However, if negative weights are present in the graph, the Bellman-Ford algorithm would be a better choice. As it can detect negative weight cycles, it may also be a good choice in these situations. Knowing the differences between these algorithms means developers won’t pick an unsuitable algorithm.
| Algorithm | Purpose | Weighted Edges | Negative Weights | Time Complexity |
| BFS | Traversal / Unweighted shortest path | No | N/A | O(V + E) |
| DFS | Exploration / Traversal | No | N/A | O(V + E) |
| Dijkstra | Weighted shortest path | Yes | No | O((V+E)logV) (binary heap) |
| Bellman-Ford | Weighted shortest path & detecting negative weight cycles | Yes | Yes | O(V × E) |
Selecting the Correct Algorithm
It is important to pick the correct algorithm for your problem, depending on the nature of the graph. If you want to explore near vertices, or find the minimum number of edges between nodes in an unweighted graph, BFS is generally a good choice. If you want to explore potential paths, investigate components of a graph, or analyse dependencies, DFS may be a better choice.
In weighted graphs with only non-negative edge weights, Dijkstra’s algorithm is usually an efficient choice for finding the shortest paths. However, if negative edge weights are included, Bellman-Ford would be a good choice. Additionally, consideration should be made for the size of the graph, memory requirements and processing time. An algorithm which is efficient in small graphs may be very inefficient for graphs with millions of vertices and edges.
Real-World Importance of Graph Algorithms
These algorithms are very useful in various contexts. Web search engines use graph algorithms to efficiently explore webpages and analyse the links between them. In social media networks, people and relations are modelled using graphs. This allows connections to be recommended to users and the way that people interact with each other can be analysed. Navigation and transport systems make use of the shortest path algorithms to find routes.
Communication networks also make use of graph structures to analyse the way in which information flows between devices. In AI graph algorithms allow information to be represented, relationships to be analysed and have applications in several machine learning processes. Graph algorithms have many applications including cyber security, logistics, research in sciences, and managing databases. As more connected data is created within digital systems, it is very important to be able to process graphs efficiently to create robust and scalable software systems.
Conclusion
The BFS, DFS, Dijkstra and Bellman-Ford algorithms are all very useful graph algorithms. The BFS visits nodes layer by layer, and is useful when finding the shortest path in an unweighted graph. The DFS goes down one path as far as possible, and then ‘backs out’ to consider alternative options. The Dijkstra algorithm finds the most efficient shortest paths in a weighted graph with positive weights. However, the Bellman-Ford algorithm can handle graphs with negative weights. It can also detect negative weight cycles.
All of these algorithms have their benefits, issues and requirements in terms of computing resources. Understanding the algorithms is therefore very important when choosing which algorithm to implement in a program. These algorithms have many real world applications such as finding paths, crawling websites, computer networks, social media and software development. If students/developers understand these basic techniques, then they will have a better understanding of data structures, creating algorithms, and creating efficient solutions to complex problems.



