Implementing Bellman-Ford and Kruskal's Algorithm for Graph Analysis

This project implements and documents the Bellman-Ford and Kruskal's algorithms for graph analysis. The program reads a graph from a text file, representing a network spanning across major Canadian cities. The Bellman-Ford algorithm is used to compute the shortest path from a given vertex to all destination vertices, simulating routing in a network. The implementation utilizes vectors, arrays, and maps as data structures. Kruskal's algorithm is then applied to calculate the minimum spanning tree of the graph, displaying the edges that connect all vertices with the minimum total weight. The project aims to demonstrate the application of these algorithms in network routing and graph theory concepts.

Bellman-Ford and Kruskal’s algorithm
Implementation Documentation
<Name>
<Institution>

The program creates a graph, and finds the shortest path as well as minimum spanning tree
through a graph, by use of Bellman-Ford algorithm. The program reads the initial state of the
graph from a text file. Bellman-Ford algorithm is then used to compute the next hop for any
packet from a given vertex to all the destination vertices. Kruskal’s algorithm is then employed
to compute and display the minimum spanning tree of the graph.
How Bellman-Ford algorithm works
The algorithm basically computes and finds the shortest distance from a given vertex. To
accomplish this, the program developed for this solution does the following;
 Reads a text file and initializes the initial graph
 Set distance to source as 0 and set infinite for all distances from the source to any
vertices.
 Create an array of distances, of size V, where V is the total number of vertices of the
graph and set all distances to infinite, with the exception of the source which we set its
distance to be 0
 Loop V - 1 times, V being number of vertices
 for each edge u - v
 check if distance of v is greater than (distance of u + UV'S weight
 update distance of v to be equal to distance of u + uv edge weight
 Finally check if the graph has any negative weights
The exact algorithm is as below;
Function receives G and S, where G is a vector of all vertexes of the graph, S is index of the source
“for each vertex V in G
distance[V] = infinite
previous[V] = NULL
distance[S] <- 0
for each vertex V in G
for each edge (U,V) in G
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
for each edge (U,V) in G
If distance[U] + edge_weight(U, V) < distance[V}
Error: Negative Cycle Exists

return distance[], previous[]”
The program uses a number of data structures.
 Vectors (std::vector<string> vertices): a vector is used to hold all the vertices read from
the file while initializing the graph; a second vector is also used to hold the weights of the
edges.
 Array: array data structure is used to hold the entire graph. In this case, a
multidimensional array is used.
 Map (map<string, int>) a map was used to hold unique cities extracted from the map. As
the map allows unique keys to be entered into it, only one instance of the city can be
entered into the map, thus allowing extraction of unique cities only.
Kruskal’s algorithm
Kruskal’s algorithm was used to compute and display the minimum spanning tree of the graph.
The algorithm takes in an input in form of a graph and evaluates it to find the subsets of all
edges, which are part of the tree that spans all vertexes and has the minimum sum of weights. To
implement this, Vector data structure was used, to hold the edges and the resulting MST
The implemented algorithm works as follows;
 It starts with an initial weighted graph
 Sort all the edges from low weight to high weight.
 Selects edge with the least weight from the graph
 Selects the next shortest edge which does not result in a cycle and adds to it
 Continue adding edges until all the vertices are connected and a Minimum Spanning Tree
(MST)
 Repeats the selection process until a spanning tree is formed