Graph Algorithms

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 sys
class 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 sys
class Graph:
def __init__(self,vertices):
self.vertices = vertices
self.graph=[]
def addEdge(self,u,v,w):
self.graph.append([u,v,w])
def bellMan(self,source):
distance = [sys.maxsize]*self.vertices
distance[source]=0
for 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]+w
for 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 sys
class 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 sys
class Graph:
def __init__(self,vertex):
self.vertex = vertex
self.graph = [[0 for x in range(self.vertex)] for x in range(self.vertex)]
def minimumDistance(self,mstSet,key):
minimum = sys.maxsize
for v in range(self.vertex):
if key[v]<minimum and mstSet[v]==False:
minimum = key[v]
min_index = v
return min_index
def 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.vertex
key[0] = 0
mstSet = [False] *self.vertex
parent = [None] *self.vertex
parent[0] =-1
for count in range(self.vertex):
u = self.minimumDistance(mstSet,key)
mstSet[u] =True
for 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] = u
self.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.