Graph-Theoretic Algorithms

5 min readNov 23, 2022

What is a Graph?

A graph consists of a finite number of vertices or nodes and a set of edges connecting these vertices. When two vertices are connected by the same edge, they are said to be adjacent.

The following are some basic definitions of graphs. Examples can be seen in Figure 1.

Order: The number of graph vertices
Size: The number of graph edges
Vertex degree: The number of edges that intersect a vertex.
Isolated vertex: A vertex in the graph that is not related to any other vertex.
Self-loop: A vertex’s edge to itself
Directed graph: A graph in which all of the edges have a direction identifying the start and end vertex.
Undirected graph: A graph with no directional edges
Weighted graph: Weights are assigned to the graph’s edges.
Unweighted graph: The graph’s edges have no weights.

Source:https://towardsdatascience.com/10-graph-algorithms-visually-explained-e57faa1336f3

Shortest Path Algorithms

The shortest path issue in graph theory is the problem of finding a path between two vertices (or nodes) in a graph that minimizes the sum of the weights of its constituent edges.

Finding the shortest way between two junctions on a road map may be described as a specific example of the shortest path issue in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the segment length.

There are types of algorithms to find the shortest path:

1)Dijkstra Algorithm(Greedy)

2)Bellman-Ford algorithm (DP)

3)Floyd–Warshall algorithm (DP)

Dijkstra Algorithm:

We can determine the shortest route between any two graph vertices using Dijkstra’s approach.

Because not all of the vertices of the graph may be included in the shortest distance between two vertices, it is different from the minimal spanning tree.

Requirements

The only graphs that Dijkstra’s Algorithm can use are those with positive weights. This is due to the fact that in order to identify the shortest path, the weights of the edges must be added during the procedure.

The algorithm won’t function properly if the network contains a negative weight. The current route to a node is designated as the quickest route to that node once it has been registered as “visited.” If the overall weight can be decreased after this step, negative weights can change this.

Working of Dijkstra’s Algorithm

Place a 0 for the current distance at the source node and an infinite for all other nodes.
Assign C as the non-visited node with the shortest current distance to serve as the current node.
Add the current distance between node C and each of its neighbors, N, together with the edge weight that connects C and N. Set it as the new current distance of N if it is less than the current distance N.
C is the current node; mark it as visited.
If any nodes have not yet been visited, move on to step 2.

Bellman-Ford algorithm

It starts with a vertex and calculates the distances that a single edge may travel between other vertices. It then looks for a path that has two edges, and so on. The Bellman-Ford algorithm employs the bottom-up approach.

More accurate values eventually retrieved an approximation to the right distance based on the “Principle of Relaxation,” until ultimately obtaining the ideal answer.

Negative weight edges can cause negative weight cycles, which shorten the overall travel distance by returning to the same place.

How Does the Bellman-Ford Algorithm Work?

The Bellman-Ford algorithm works by drastically underestimating the route length from the initial vertex to all other vertices. The algorithm then relaxes such estimates repeatedly by uncovering new pathways that are shorter than the previously overestimated paths.

By repeating this method for all vertices, you can assure that the outcome is optimal.

Make a list of all the edges in the graph. This is straightforward if the graph is represented as an adjacency list.
The number of iterations is calculated using “V — 1.” Because the shortest distance to an edge can only be changed to V — 1, the number of iterations will grow by the same number of vertices.
Start with an arbitrary vertex and a distance of zero. All other nodes should be allocated infinite because you are inflating the real distances.

Now, Relax the route lengths for the vertices for each edge u-v:

If distance[v] is exceeds distance[u] + edge weight uv, then

distance[v] = distance[u] + edge weight uv

If the new distance is shorter than the old one, the distance for each Edge should be updated in each iteration. The total distance from the beginning node to this specific node is the distance to each node.
Alliterations must be examined to guarantee that all feasible pathways are evaluated. If you do this, you will end up with the shortest distance.

Floyd-Warshall

A weighted graph’s Floyd-Warshall algorithm is used to determine the shortest route between all of the vertex pairs. Both the directed and undirected weighted graphs can be solved using this approach. However, it is ineffective for graphs with negative cycles (where the sum of the edges in a cycle is negative).

Algorithm:

As a first step, set the solution matrix to be the same as the input graph matrix.
The solution matrix is then updated by treating each vertex as an intermediate vertex.
The plan is to select each vertex one at a time and update any shortest paths that use the selected vertex as an intermediate vertex.
Vertices 0, 1, 2,.., k-1 are already taken into consideration when vertex number k is chosen as an intermediate vertex.
There are two potential outcomes for every pair of source and destination vertices I j), respectively.
The shortest path from I to j does not include k as an intermediary vertex. We maintain the current dist[i][j] value.
In the shortest path from I to j, k is an intermediate vertex. As dist[i][k] + dist[k][j], we update the value of dist[i][j]. When dist[i][j] > dist[i][k] + dist[k][j].

Comparison: