Graph Algorithms

Nilay Paul
5 min readMay 22, 2021

--

In this blog we will discuss about elementary path finding algorithms .

In the next blog related to path finding we will discuss about A* algorithm.

Dijkstra Algorithm — — — — — — — — — — — — — — — — — — — — -

This is a single source shortest path algorithm .

Python implementation — -

We will make a list that keeps track of visited vertex.

We will have a list with initial distance infinite for all the entries.

The distance of the source is 0 , so that one is chosen first.

import sysclass Graph:   def __init__(self,vertices):      self.vertices = vertices      self.graph = [[0 for column in range(self.vertices)] for row in range(self.vertices)]  def minDistance(self,sptSet,distance):      minimum_distance=sys.maxsize      for i in range(len(sptSet)):      if distance[i]<minimum_distance and sptSet[i]==False:        minimum_distance=distance[i]        min_index=i      return min_index  def Dj(self,source):     sptSet = [False] *self.vertices     distance = [sys.maxsize]*self.vertices     distance[source]=0     for count in range(len(sptSet)):         u = self.minDistance(sptSet,distance)         sptSet[u]=True    for v in range(self.vertices):       if self.graph[u][v]>0 and sptSet[v]==False and distance[v]>distance[u]+self.graph[u][v]:       distance[v]=distance[u]+self.graph[u][v]       print(distance)graph = Graph(8)graph.graph= [[0, 4, 0, 0, 0, 0, 0, 8, 0],[4, 0, 8, 0, 0, 0, 0, 11, 0],[0, 8, 0, 7, 0, 4, 0, 0, 2],[0, 0, 7, 0, 9, 14, 0, 0, 0],[0, 0, 0, 9, 0, 10, 0, 0, 0],[0, 0, 4, 14, 10, 0, 2, 0, 0],[0, 0, 0, 0, 0, 2, 0, 1, 6],[8, 11, 0, 0, 0, 0, 1, 0, 7],]graph.Dj(0)

C# implementation

using System;class Graph{public int vertices;public int[,] graph=new int[100,100];public Graph(int vertices){this.vertices=vertices;this.graph=new int[this.vertices,this.vertices];}public int ComputeMindistance(int[] distance,bool[] sptSet){int min_index=-1;int minimum=int.MaxValue;for(int i=0;i<this.vertices;i++){if(distance[i]<=minimum && sptSet[i]==false){minimum=distance[i];min_index=i;}}return min_index;}public void Dijkarat(int source){bool[] sptSet = new bool[this.vertices];int[] distance = new int[this.vertices];for(int i=0;i<this.vertices;i++){distance[i]=int.MaxValue;sptSet[i]=false;}distance[source]=0;for(int i=0;i<sptSet.Length-1;i++){int u = ComputeMindistance(distance,sptSet);sptSet[u]=true;for(int v=0;v<this.vertices;v++){if(this.graph[u,v]>0 && sptSet[v]==false && distance[v]>distance[u]+this.graph[u,v]){distance[v]=distance[u]+this.graph[u,v];}}}for(int i=0;i<this.vertices;i++){System.Console.Write("  "+distance[i]);}}}class Tester{public static void Main(){Graph graph=new Graph(9);graph.graph=new int[,]{{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};graph.Dijkarat(0);}}

Bellman Ford Algorithm — — — — — — — — — — — — — — — — — — — — —

In case of Djikstra’s algorithm the negative weight of an edge may cause problem so in that case Bellman Ford’s algorithm can be used.

Python implementation (Make sure to indent the code )

import sysclass Graph:def __init__(self,vertices):self.vertices = verticesself.graph=[]def addEdge(self,u,v,w):self.graph.append([u,v,w])def bellMan(self,source):distance = [sys.maxsize]*self.verticesdistance[source]=0for i in range(self.vertices-1):for u,v,w in self.graph:if distance[u]!=sys.maxsize and distance[v]>distance[u]+w:distance[v]=distance[u]+wfor u,v,w in self.graph:if distance[u]!=sys.maxsize and distance[v]>distance[u]+w:print("Negative cycle present")print(distance)graph = Graph(5)graph.addEdge(0,1,-1)graph.addEdge(0,2,4)graph.addEdge(1,2,3)graph.addEdge(1,3,2)graph.addEdge(1,4,2)graph.addEdge(3,2,5)graph.addEdge(3,1,1)graph.addEdge(4,3,-3)graph.bellMan(0)

Floyd-Warshall Algorithm — — — — — — — — — — — — — — — — — — — -

All pair shortest path algorithm.

We express a graph in terms of adjacency matrix and dynamically by taking certain decision get final result in terms of resultant matrix.

Python -------------import sysclass Graph:    def __init__(self,vertex):       self.vertex=vertex       self.graph = [[0 for x in range(vertex)] for x in range(vertex)]   def FloydW(self):      for k in range(self.vertex):        for i in range(self.vertex):          for j in range(self.vertex):               self.graph[i][j] = min(self.graph[i][j],self.graph[i][k]+self.graph[k][j])     print(self.graph)graph = Graph(4)graph.graph = [[0,5,sys.maxsize,10],[sys.maxsize,0,3,sys.maxsize],[sys.maxsize,sys.maxsize,0,1],[sys.maxsize,sys.maxsize,sys.maxsize,0]]print(graph.graph)graph.FloydW()

C# implementation

using System;class Floyd{public static void Main() {int[,] graph = new int[4,4]{{0,5,999,10},{999,0,3,999},{999,999,0,1},{999,999,999,0}};FloydCalculation(graph,4);}public static void FloydCalculation(int[,] graph,int vertex){for(int k=0;k<vertex;k++){for(int i=0;i<vertex;i++){for(int j=0;j<vertex;j++){graph[i,j]  = Math.Min(graph[i,j],graph[i,k]+graph[k,j]);}}}for(int i=0;i<vertex;i++){for(int j=0;j<vertex;j++){System.Console.Write(graph[i,j]+" ");}System.Console.WriteLine();}}}

Prim’s Algorithm — — — — — — — — — — — — — — — — — — — — — — — —

To find minimum spanning tree we can use Prim’s algorithm.

  • Spanning tree — — Subset of a graph with V vertex and |V-1| edges.

To keep track of the visited vertex we will have a list / array.

The entries of distance vector will be infinite.

The source distance is 0 so that it becomes the first element to be selected.

Parent list will keep track of the initial vertex of an edge that will produce minimum spanning tree.

Python implementation — — — — — — — — — — — — — — — — — — —

import sysclass Graph:def __init__(self,vertex):self.vertex = vertexself.graph = [[0 for x in range(self.vertex)] for x in range(self.vertex)]def minimumDistance(self,mstSet,key):minimum = sys.maxsizefor v in range(self.vertex):if key[v]<minimum and mstSet[v]==False:minimum = key[v]min_index = vreturn min_indexdef printMe(self,parent):print("Edge\t Weight")for v in range(1,self.vertex):print(parent[v] ," ",v,"\t",self.graph[v][parent[v]])def calculateMst(self):key = [sys.maxsize]*self.vertexkey[0] = 0mstSet = [False] *self.vertexparent = [None] *self.vertexparent[0] =-1for count in range(self.vertex):u = self.minimumDistance(mstSet,key)mstSet[u] =Truefor v in range(self.vertex):if mstSet[v]==False and self.graph[u][v]>0 and key[v]> self.graph[u][v]:key[v] =self.graph[u][v]parent[v] = uself.printMe(parent)graph = Graph(4)graph.graph = [[0,2,0,6,0],[2,0,3,8,5],[0,3,0,0,7],[6,8,0,0,9]]graph.calculateMst()

C# implementation

class Graph{public int vertex;public int[,] graph;public Graph(int vertex){this.vertex = vertex;this.graph = new int[this.vertex,this.vertex];}public  int FindMin(bool[] mstSet,int[] key){int minimum = int.MaxValue;int min_index=-1;for(int i=0;i<5;i++){if(key[i]<minimum && mstSet[i]==false){minimum = key[i];min_index=i;}}return min_index;}public void printDetails(int[] parent){System.Console.WriteLine("Edge\tWeight");for(int i=1;i<5;i++){System.Console.WriteLine(parent[i]+" "+i+" \t"+this.graph[i,parent[i]]);}}public void CalculateMst(){bool[] mstSet = new bool[this.vertex];int[] key = new int[this.vertex];int[] parent = new int[this.vertex];for(int i=0;i<this.vertex;i++){mstSet[i] = false;key[i] = int.MaxValue;}key[0]=0;parent[0]=-1;for(int i=0;i<this.vertex;i++){int u = FindMin(mstSet,key);mstSet[u] = true;for(int v=0;v<this.vertex;v++){if(this.graph[u,v]>0 && mstSet[v]==false && key[v]>this.graph[u,v]){key[v] = this.graph[u,v];parent[v]=u;}}}printDetails(parent);}}class Tester{public static void Main(){Graph graph = new Graph(5);graph.graph=new int[,]{{0,2,0,6,0},{2,0,3,8,5},{0,3,0,0,7},{6,8,0,0,9},{0,5,7,9,0}};graph.CalculateMst();}}

Note : Python codes may cause indentation error because of improper indentation of medium . You can always refer to C# ones.

Take care , Bye.

--

--