Homework SourseImplement Dijkstras algorithm using the graph class you impl
Implement
Dijkstra’s algorithm using the graph class you implemented in
HW
#5 and
a priority
queue
you have
implemented
earlier this semester
.
Y
ou
r
program will read the graph from a text file like
what we did in
HW
#
5
. You can use
graph.txt from HW
#5
to test your program. Make the header of
the method as Dijsktra(G, v), where v is the starting vertex.
Further, write a method that prints the
shortest path betw
een any two vertices. Example: s
hortestPath(G,
x
,
y
).
Write a main method t
o test
your program.
Instructions:
1.
Y
ou can use C#
or Java programming languages. No other language is allowed or accepted
HW#5 Question
Q1)
(6
0 points)
Implement a
graph ADT by defining a class “Graph” with the operations
below. You
r
ADT should accept either a directed or undirected graph.
isDirect():
tests if the graph is a digraph
. Returns Boolean value.
adjacent(v,
u): tests whether there is an edge from the vertex v to u. returns Boolean value.
n
eighbors(v): returns the list of all vertices that are a destination of an edge from v.
addVertex(v): adds the vertex v to the graph if it is not already in the
graph, otherwise an error
message to be thrown.
removeVertex(v): removes vertex v from the graph, if it is there.
When a vertex is removed, all
edges associated with that vertex should be deleted as well.
addEdge(v,
u): adds the edge that starts from v and
ends at u.
addEdge(v, u, w):
adds the edge t
hat starts from v and ends at u with weight w.
removeEdge(v,
u): remove the edge that connects v and u.
getWeight
(v,
u): returns the weight of the edge from v to u.
setWeight
(v,
u): sets the weight of the edge
from v to u.
isEmpty(): check whether the graph is empty or not.
isComplete(): checks whether the graph is complete or not.
vertices():returns the list of vertices in the graph (i.e
.
, array, vector,..)
edges(): returns the list of edges in the graph.
d
egree(v): return the degree of vertex v.
size(): returns the number of vertices in the graph.
nEdges(): returns the number of edges in the graph.
c
lear(): Reinitializes the graph to be empty, freeing any heap storage.
vertexExists(v): tests whether a verte
x is in the graph or not. Returns true or false.
p
rint(): displays the list of vertices, edges and their weights if the graph is weighted.
Your ADT should contain at least these constructors:
Graph(), creates a graph with zero vertices.
Graph(n), creates
a graph with n vertices.
Graph(n, digraph), where digraph is a Boolean value if true means
a
directed graph.
Q2) (50 points)
Write a main method that r
ead
s
the graph.txt file that contains the information of
directed weighted
graph.
The file is formatted
as the following:
First line is the number of vertices in the graph.
Second line contains the vertices in the graph.
Each
following line contains the edges and the weights. For example: a b 4, means an ed
ge from a to be with
weight = 4.
After
reading the f
ile and creating
the graph perform the following operations in the same order:
•
removeVertex(h)
•
print if the graph is complete or not (i.e., the graph is complete or the graph is not complete)
•
print number of edges in the graph (i.e., number of edges is xx)
•
print if there is a link from a to f (i.e., there is a link from a to f or there is no link from a to f)
•
print the weight of the edge b
à
h (i.e., the weight of the edge from b to h is xx)
•
print the degree of c (i.e., the degree of c is xx)
•
print number of
vertices in the graph (i.e., the graph contains xx vertices)
•
addVertex(k)
•
add(k,a,5)
•
add (g, k, 2)
•
setWeight(a, c, 7)
•
print the graph on the screen. Use the same format in the graph.txt to display information about
the graph on the screen
HW#5 answer
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace Bond_HW5
{
public class Vertex
{
public string name;
public double distance;
public List<Edge> edges;
public Vertex()
{
name = \"\";
edges = new List<Edge>();
}
public Vertex(string nm)
{
this.name = nm;
edges = new List<Edge>();
}
}
public class Edge
{
public Vertex target;
public double weight;
public Edge()
{
target = null;
weight = 0;
}
public Edge(Vertex target, double weight)
{
this.target = target;
this.weight = weight;
}
}
public class Graph
{
Vertex[] graph;
int nVertices;
bool isdirected;
public Graph()
{
nVertices = 0;
graph = new Vertex[nVertices];
isdirected = false;
}
public Graph(int n)
{
isdirected = false;
this.nVertices = n;
graph = new Vertex[nVertices];
}
public Graph(int n, bool digraph)
{
isdirected = digraph;
this.nVertices = n;
graph = new Vertex[nVertices];
}
public bool isDirect()
{
if (this.isdirected == true)
{
return true;
}
else
{
return false;
}
}
public bool adjacent(Vertex v, Vertex u)
{
bool vexists = vertexExists(v);
bool uexists = vertexExists(u);
if(vexists && uexists)
{
if (v.edges.Exists(x => x.target.name == u.name))
{
return true;
}
else
{
return false;
}
}
else
return false;
}
public List<Vertex> neighbors(Vertex v)
{
List < Vertex > a = new List<Vertex>();
foreach (Edge e in v.edges.ToArray())
{
a.Add(e.target);
}
return a ;
}
public void addVertex(Vertex v)
{
if(this.vertexExists(v))
{
Console.WriteLine(\"Error, vertex already exists\");
}
else
{
if(graph[0]== null)
{
graph[0] = v;
}
else
{
int i = 1;
while(graph[i]!= null && i < nVertices)
{
i++;
}
if(i>= nVertices)
{
Console.WriteLine(\"Graph full\");
}
else
{
graph[i] = v;
}
}
}
}
public void removeVertex(Vertex v)
{
for (int i = 0; i < nVertices; i++)
{
if (graph[i] != null)
{
if (this.graph[i].name == v.name)
{
graph[i] = null;
}
}
}
}
public void addEdge(Vertex v, Vertex u)
{
bool vexists = vertexExists(v);
bool uexists = vertexExists(u);
if (vexists && uexists)
{
if (isdirected == true)
{
Edge vu = new Edge(u, 0);
v.edges.Add(vu);
}
else
{
Edge vu = new Edge(u, 0);
Edge uv = new Edge(v, 0);
v.edges.Add(vu);
u.edges.Add(uv);
}
}
else if (vexists == true && uexists == false)
{
Console.WriteLine(\"Error: Vertex \'u\' does not exist, please add using the addVertex Function\");
}
else if (vexists == false && uexists == true)
{
Console.WriteLine(\"Error: Vertex \'v\' does not exist, please add using the addVertex Function\");
}
else if (vexists == false && uexists == false)
{
Console.WriteLine(\"Error: Neither vertex exist, please add using the addVertex Function\");
}
}
public void addEdge(Vertex v, Vertex u, int w)
{
bool vexists = vertexExists(v);
bool uexists = vertexExists(u);
if (vexists && uexists)
{
if (isdirected == true)
{
for (int i = 0; i < nVertices; i++)
{
if (graph[i] != null && graph[i].name == v.name)
{
Edge vu = new Edge(u, w);
graph[i].edges.Add(vu);
}
}
}
else
{
Edge vu = new Edge(u, w);
Edge uv = new Edge(v, w);
v.edges.Add(vu);
u.edges.Add(uv);
}
}
else if (vexists == true && uexists == false)
{
Console.WriteLine(\"Error: Vertex \'u\' does not exist, please add using the addVertex Function\");
}
else if (vexists == false && uexists == true)
{
Console.WriteLine(\"Error: Vertex \'v\' does not exist, please add using the addVertex Function\");
}
else if (vexists == false && uexists == false)
{
Console.WriteLine(\"Error: Neither vertex exist, please add using the addVertex Function\");
}
}
public double getWeight(Vertex v, Vertex u)
{
Edge temp = new Edge();
for(int i = 0; i <nVertices; i++)
{
if(graph[i] == null || graph[i].name != v.name)
{
continue;
}
else if(graph[i].name == v.name)
{
temp = graph[i].edges.Find(x => x.target.name == u.name);
}
}
return temp.weight;
}
public void setWeight(Vertex v, Vertex u, double w)
{
Edge temp = new Edge();
if (isdirected)
{
for (int i = 0; i < nVertices; i++)
{
if (graph[i] == null || graph[i].name != v.name)
{
continue;
}
else if (graph[i].name == v.name)
{
temp = graph[i].edges.Find(x => x.target.name == u.name);
temp.weight = w;
}
}
}
else
{
for (int i = 0; i < nVertices; i++)
{
if (graph[i] == null || graph[i].name != v.name)
{
continue;
}
else if (graph[i].name == v.name)
{
temp = graph[i].edges.Find(x => x.target.name == u.name);
temp.weight = w;
}
}
for (int j = 0; j < nVertices; j++)
{
if (graph[j] == null || graph[j].name != u.name)
{
continue;
}
else if (graph[j].name == u.name)
{
temp = graph[j].edges.Find(y => y.target.name == u.name);
temp.weight = w;
}
}
}
}
public bool isEmpty()
{
if (nVertices == 0)
return true;
else
return false;
}
public bool isComplete()
{
Edge[] a;
double sum = 0;
double n = graph.Length;
foreach (Vertex x in graph)
{
if (x != null)
{
a = x.edges.ToArray();
sum += a.Length;
}
}
if(sum < ((n*(n-1)/2)))
{
return false;
}
else
return true;
}
public Vertex[] vertices()
{
return graph;
}
public string edges()
{
string elist = \"\";
Edge[] arr;
foreach (Vertex x in graph)
{
if (x != null)
{
arr = x.edges.ToArray();
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].target != null)
{
elist = elist+x.name + arr[i].target.name + \"(\"+arr[i].weight+\")\";
elist += \"|\";
}
}
}
}
return elist;
}
public int degree(Vertex V)
{
if (isdirected)
{
int counter = 0;
for (int i = 0; i < nVertices; i++)
{
if (graph[i] != null && graph[i].name == V.name)
{
foreach (Edge e in graph[i].edges)
{
counter++;
}
}
}
return counter;
}
else
{
int counter = 0;
for (int i = 0; i < nVertices; i++)
{
if (graph[i] != null && graph[i].name == V.name)
{
foreach (Edge e in graph[i].edges)
{
counter++;
}
}
}
return counter;
}
}
public double size()
{
return graph.Length;
}
public double Nedges()
{
Edge[] a;
double sum = 0;
double n = graph.Length;
foreach (Vertex x in graph)
{
if (x != null)
{
a = x.edges.ToArray();
sum += a.Length;
}
}
if (isdirected)
{
return sum;
}
else
{
return sum / 2;
}
}
public void clear()
{
for (int i = 0; i < nVertices; i++)
{
graph[i] = null;
}
}
public bool vertexExists(Vertex v)
{
for(int i =0; i< nVertices; i++)
{
if (graph[i] != null)
{
if (graph[i].name == v.name)
return true;
}
else
{
continue;
}
}
return false;
}
public void print()
{
Console.WriteLine(\"Vertices: \");
foreach (Vertex v in graph)
{
if (v != null)
{
Console.WriteLine(\"name: \" + v.name);
}
}
Console.WriteLine(\"Edges: \");
Console.WriteLine(edges());
}
}
class Program
{
static void Main(string[] args)
{
/*
Graph a = new Graph(10, false);
Vertex b = new Vertex();
Vertex c = new Vertex();
c.name = \"c\";
b.name = \"b\";
a.addVertex(b);
a.addVertex(c);
a.addEdge(b, c, 10);
a.print();*/
// INput from txt file
StreamReader Reader = new StreamReader(\"graph.txt\");
int numvert;
string[] vertchars;
List<string> edgecreator = new List<string>();
numvert = int.Parse(Reader.ReadLine());
vertchars = new string[numvert];
Graph myGraph = new Graph(numvert, true);
string thechars = Reader.ReadLine();
vertchars = thechars.Split(\' \');
foreach(string character in vertchars)
{
Vertex adder = new Vertex(character);
myGraph.addVertex(adder);
}
string edgeReader;
while((edgeReader = Reader.ReadLine())!= null)
{
edgecreator.Add(edgeReader);
}
string[] b = edgecreator.ToArray();
foreach(string sent in b)
{
string[] splitter = sent.Split(\' \');
Vertex a = new Vertex(splitter[0]);
Vertex c = new Vertex(splitter[1]);
myGraph.addEdge(a, c, int.Parse(splitter[2]));
}
Vertex tester = new Vertex();
Vertex tester2 = new Vertex();
//print the weight of edge b to h
tester.name = \"b\";
tester2.name = \"h\";
double theWeight = myGraph.getWeight(tester, tester2);
Console.WriteLine(\"The weight from b->h is {0}\", theWeight);
//remove vertex h
myGraph.removeVertex(tester2);
//print whether or not the graph is complete
bool comp = myGraph.isComplete();
if(comp)
{
Console.WriteLine(\"the graph is complete\");
}
else
{
Console.WriteLine(\"the graph is not complete\");
}
//print whethether there is a link from a to f
tester = new Vertex(\"a\");
tester2 = new Vertex(\"f\");
comp = myGraph.adjacent(tester, tester2);
if (comp)
{
Console.WriteLine(\"there is a link from a to f\");
}
else
{
Console.WriteLine(\"there is not a link from a to f\");
}
//print the degree of c
Vertex tester3 = new Vertex(\"c\");
Console.WriteLine(\"the out degree of c is {0}\", myGraph.degree(tester3));
//print number of vertices
Console.WriteLine(\"The number of vertices is {0}\", myGraph.vertices().Length);
//add vertex k
tester2 = new Vertex(\"k\");
myGraph.addVertex(tester2);
//add edge k,a,5
myGraph.addEdge(tester2, tester);
//add edge g k 2
Vertex tester4 = new Vertex(\"g\");
myGraph.addEdge(tester4, tester2);
//set weight a,c,7
myGraph.setWeight(tester, tester3, 7);
//print graph
myGraph.print();
}
}
}
Solution
Please Find the Solution in Java
import java.io.*;
import java.util.*;
class Edge
{
public int dest;
public int weight;
public Edge(int dest,int weight)
{
this.dest=dest;
this.weight=weight;
}
}
class Graph
{
public int V;
LinkedList<Edge>[] myList;
public Graph(int V)
{
this.V=V;
myList=new LinkedList[V+1];
for(int i=1;i<=V;i++)
myList[i]=new LinkedList();
}
public void addEdge(int src,int dest,int weight)
{
Edge e1=new Edge(dest,weight);
Edge e2=new Edge(src,weight);
myList[src].add(e1);
myList[dest].add(e2);
}
}
class Node
{
public int value;
public int dist;
public Node(int value,int dist)
{
this.value=value;
this.dist=dist;
}
}
class minHeap
{
public int capacity;
public int size;
Node[] heap;
int[] pos;
public minHeap(int capacity)
{
this.capacity=capacity;
this.size=capacity;
heap=new Node[capacity+1];
pos=new int[capacity+1];
for(int i=0;i<capacity;i++)
{
heap[i]=new Node(i+1,Integer.MAX_VALUE);
pos[i+1]=i;
}
}
public int left(int index)
{
return 2*index+1;
}
public int right(int index)
{
return 2*index+2;
}
public int parent(int index)
{
return ((index-1)/2);
}
public void decreaseKey(Node nd)
{
int index=pos[nd.value];
if(nd.dist<heap[index].dist)
{
heap[index]=nd;
while(index>0&&heap[parent(index)].dist>heap[index].dist)
{
pos[heap[parent(index)].value]=index;
pos[heap[index].value]=parent(index);
Node temp=heap[parent(index)];
heap[parent(index)]=heap[index];
heap[index]=temp;
index=parent(index);
}
}
}
public Node extractMin()
{
if(size==1)
{
size=0;
return heap[0];
}
else
{
Node root=heap[0];
Node leaf=heap[size-1];
heap[0]=leaf;
pos[root.value]=size-1;
pos[leaf.value]=0;
min_hippfy(0);
size=size-1;
return root;
}
}
public void min_hippfy(int i)
{
int left=left(i);
int right=right(i);
int smallest=i;
if(left<=(size-1)&&heap[left].dist<heap[smallest].dist)
{
smallest=left;
}
if(right<=(size-1)&&heap[right].dist<heap[smallest].dist)
{
smallest=right;
}
if(smallest!=i)
{
Node temp1=heap[smallest];
Node temp2=heap[i];
heap[smallest]=temp2;
heap[i]=temp1;
pos[temp1.value]=i;
pos[temp2.value]=smallest;
min_hippfy(smallest);
}
}
public boolean isInHeap(int x)
{
if(x<size)return true;
else return false;
}
}
public class Main
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int n=in.nextInt(); // Number of Nodes starting with 1
int m=in.nextInt(); // Number of Edges
Graph g=new Graph(n);
for(int i=0;i<m;i++)
{
int x=in.nextInt(); //From Node
int y=in.nextInt(); //To Node
int w=in.nextInt(); //Weight
g.addEdge(x,y,w); //Add Edge
}
int s=in.nextInt(); //Can use any Node as Start Node
minHeap mp=new minHeap(n);
Node firstNode=new Node(s,0);
mp.decreaseKey(firstNode);
int[] distance=new int[n+1]; //Result, Shortest Distance from given Start Node
while(mp.size!=0)
{
Node u=mp.extractMin();
distance[u.value]=u.dist;
Iterator<Edge> j=g.myList[u.value].iterator();
while(j.hasNext())
{
Edge adj=j.next();
if(mp.isInHeap(mp.pos[adj.dest])&&u.dist!=Integer.MAX_VALUE&&adj.weight+u.dist<mp.heap[mp.pos[adj.dest]].dist)
{
Node adjNode=new Node(adj.dest,adj.weight+u.dist);
mp.decreaseKey(adjNode);
}
}
}
for(int i=1;i<=n;i++)
{
if(distance[i]==Integer.MAX_VALUE)
System.out.print(\"-1 \");
else
{
if(i!=s)
System.out.print(distance[i]+\" \");
}
}
System.out.println();
}
}
Sample Input
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1
Output:
