Assignment Help - homework help

  Concepts of Kruskals algorithm, Prims algorithm and Dijkstra Algorithm

Kruskal's algorithm:

We will begin with Kruskal's algorithm, which is simplest to understand and probably the best one for resolving problems by hand.

Kruskal's algorithm:
    sort the edges of G in increasing order by length
    keep a subgraph S of G, initially empty
    for each edge e in sorted order
        if the endpoints of e are disconnected in S
        add e to S
    return S

Note that, whenever you add an edge (u,v), it is always the smallest connecting the portion of S reachable from u with the rest of G, therefore by the lemma it should be portion of the MST.

This algorithm is recognized as a greedy algorithm, since it selects at each step the cheapest edge to add to S. You must be very careful when trying to employ greedy algorithms to resolve other problems, as it generally doesn't work. Example: if you want to find the shortest path from a to b, it might be a bad idea to keep taking shortest edges. The greedy idea just works in Kruskal's algorithm as of the key property we proved.

Analysis: The line testing whether two endpoints are disengaged looks like it must be slow (that is, linear time per iteration, or O(mn) total). The slowest portion turns out to be the sorting step, that takes O(m log n) time.

Prim's algorithm:

Instead of build a sub-graph one edge at a time, Prim's algorithm forms a tree one vertex at a time. 

    Prim's algorithm:
    let T be a single vertex x
    while (T has fewer than n vertices) {
        find the smallest edge connecting T to G-T
        add it to T
    }
Example of Prim's algorithm in C language:
/* usedp=>how many points already used 
   p->array of structures, consisting x,y,& used/not used
   this problem is to get the MST of graph with n vertices
   which weight of an edge is the distance between 2 points */
usedp=p[0].used=1; /* select arbitrary point as starting point */
while (usedp<n) {
  small=-1.0;
 
  for (i=0;i<n;i++) if (p[i].used)
    for (j=0;j<n;j++) if (!p[j].used) {
      length=sqrt(pow(p[i].x-p[j].x,2) + pow(p[i].y-p[j].y,2));
 
      if (small==-1.0 || length<small) {
        small=length;
        smallp=j;
      }
    }
  minLength+=small;
  p[smallp].used=1;
  usedp++ ;
}

Dijkstra Algorithm:

Dijkstra's algorithm (introduced by Edsger W. Dijkstra) solves the trouble of finding the shortest path from a point in a graph (that is, the source) to a destination. It turns out that one can determine the shortest paths from a given source to all points in a graph in similar time; therefore this problem is termed as the Single-source shortest paths problem.

There will as well be no cycles as a cycle would state more than one path from the chosen vertex to at least one other vertex. For a graph, G = (V,E); where V is a set of vertices and E is a set of edges.

Dijkstra's algorithm maintains two sets of vertices: S (that is, the set of vertices whose shortest paths from the source have already been determined) and V-S (that is, the remaining vertices). The other data structures required are: d (that is, array of best estimates of shortest path to each and every vertex) & pi (that is, an array of predecessors for each and every vertex).

The fundamental mode of operation is:

A) Initialise d and pi, 
B) Set S to empty,
C) As there are still vertices in V-S,
D) Sort the vertices in V-S according to the current most excellent estimate of their distance from source, 
E) Add u, the closest vertex in V-S, to S, 
F) Relax all vertices still in V-S joined to u 
 
DIJKSTRA(Graph G,Node s)
  initialize_single_source(G,s)
  S:={ 0 }       /* Make S empty */
  Q:=Vertices(G) /* Put the vertices in a PQ */
  while not Empty(Q)
    u:=ExtractMin(Q);
    AddNode(S,u); /* Add u to S */
    for each vertex v which is Adjacent with u
      relax(u,v,w)

Bellman-Ford Algorithm:

A more comprehensive single-source shortest paths algorithm that can find the shortest path in a graph with negative weighted edges. When there is no negative cycle in the graph, this algorithm will revises each d[v] with the shortest path from s to v, fill up the predecessor list "pi", and return TRUE. Though, if there is a negative cycle in given graph, this algorithm will return FALSE.

BELLMAN_FORD(Graph G,double w[][],Node s)
  initialize_single_source(G,s)
  for i=1 to |V[G]|-1
    for each edge (u,v) in E[G]
      relax(u,v,w)
 
  for each edge (u,v) in E[G]
    if d[v] > d[u] + w(u, v) then
      return FALSE
  return TRUE

Floyd Warshall:

Given a directed graph, the Floyd-Warshall All Pairs Shortest Paths algorithm evaluates the shortest paths between each and every pair of nodes in O(n^3). In this, we list down the Floyd Warshall and its variant with the source codes.

Given:

w : edge weights 
d : distance matrix 
p : predecessor matrix 
w[i][j] = length of direct edge between i and j
d[i][j] = length of shortest path between i and j
p[i][j] = on a shortest path from i to j, p[i][j] is the last node before j.

Initialization:

for (i=0; i<n; i++)
  for (j=0; j<n; j++) {
    d[i][j] = w[i][j];
    p[i][j] = i;
  }
for (i=0; i<n; i++)  d[i][i] = 0;
The Algorithm
for (k=0;k<n;k++) /* k -> is the intermediate point */
  for (i=0;i<n;i++) /* start from i */
    for (j=0;j<n;j++) /* reaching j */
      /* if i-->k + k-->j is smaller than the original i-->j */
      if (d[i][k] + d[k][j] < d[i][j]) {
        /* then reduce i-->j distance to the smaller one i->k->j */
        graph[i][j] = graph[i][k]+graph[k][j];
        /* and update the predecessor matrix */
        p[i][j] = p[k][j];
      }

In k-th iteration of the outer loop, we try to enhance the currently recognized shortest paths by considering k as an intermediate node. As a result, after the k-th iteration we know such shortest paths which only contain intermediate nodes from the set {0, 1, 2,...,k}.

After all n iterations we recognize the real shortest paths. 

Constructing a Shortest Path
print_path (int i, int j) {
  if (i!=j)    print_path(i,p[i][j]);
  print(j);
}

Eulerian Cycle & Eulerian Path:

Euler Cycle:

Input: Connected, directed graph G = (V,E)
Output: A cycle which traverses every edge of G precisely once, though it might visit a vertex more than once.

Theorem: A directed graph possesses an Eulerian cycle if:
a) It is connected
b) For all {v} in {V} indegree(v) = outdegree(v) 
 
Euler Path:

Input: Connected, directed graph G = (V, E)
Output: The path from v1 to v2, which traverses each and every edge of G precisely once, though it might visit a vertex more than once.

Theorem: The directed graph acquires an Eulerian path if:

a) It is connected

b) For all {v} in {V} indegree(v) = outdegree(v) with possible exception of two vertices v1,v2 in that case,
i) indegree(v1) = outdegree(v2) + 1
ii) indegree(v2) = outdegree(v1) - 1

Latest technology based Programming Languages Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.
Home | Company Overview | Services | Discover Q&A | Sitemap | Contact Us | T & C | Refund Policy | Copyright Policy | Blog | Q&A | Directory

©TutorsGlobe All rights reserved 2022-2023.