Implement Moore\'s algorithm for shortest path described in Chapter 7. Use the d

Question

Implement Moore's algorithm for shortest path described in Chapter 7. Use the distributed workpool version. The master process (P0) should read the adjacency matrix from a text file and start the process by examining the source (i.e., the source vertex is assigned to P0). The format of the input file should be:

n  -- the number of vertexes

The first row of the matrix, n numbers separated by spaces

…

The nth row of the matrix

Use -1 to indicate infinity in the matrix.

Once the program terminates, the master process P0 gathers the distances from other processes and prints them on the screen.

Note: Although the number of processes to create to run each case has to be equal to the number of vertexes in the given problem, the program should be designed as a general program that can take any input size (the number of vertexes can differ from case to case).

Termination detection: Use P0 as the root. When a process computes a new distance to a vertex, it sends the new distance to the corresponding process and becomes its parent. Upon receiving the new distance, the child process determines whether an update should be done to the current shortest distance. If no update to be done, the process sends an acknowledgement to the parent, otherwise it updates the distance and computes new distances to nearby vertexes and activates the corresponding processes (and becomes their parent). When the parent has received acknowledgements from all children, it sends the acknowledgement to its parent. When the root receives acknowledgements from all its children, it sends a termination signal to all processes.

Turn in the tested program (.c file)

Explanation / Answer

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <limits.h>

// a structure to represent a weighted edge in graph

struct Edge

{

    int src, dest, weight;

};

// a structure to represent a connected, directed and weighted graph

struct Graph

{

    // V-> Number of vertices, E-> Number of edges

    int V, E;

    // graph is represented as an array of edges.

    struct Edge* edge;

};

// Creates a graph with V vertices and E edges

struct Graph* createGraph(int V, int E)

{

    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );

    graph->V = V;

    graph->E = E;

    graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

    return graph;

}

// A utility function used to print the solution

void printArr(int dist[], int n)

{

    printf("Vertex   Distance from Source ");

    for (int i = 0; i < n; ++i)

        printf("%d %d ", i, dist[i]);

}

// The main function that finds shortest distances from src to all other

// vertices using Bellman-Ford algorithm. The function also detects negative

// weight cycle

void BellmanFord(struct Graph* graph, int src)

{

    int V = graph->V;

    int E = graph->E;

    int dist[V];

    // Step 1: Initialize distances from src to all other vertices as INFINITE

    for (int i = 0; i < V; i++)

        dist[i]   = INT_MAX;

    dist[src] = 0;

    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src

    // to any other vertex can have at-most |V| - 1 edges

    for (int i = 1; i <= V-1; i++)

    {

        for (int j = 0; j < E; j++)

        {

            int u = graph->edge[j].src;

            int v = graph->edge[j].dest;

            int weight = graph->edge[j].weight;

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])

                dist[v] = dist[u] + weight;

        }

    }

    // Step 3: check for negative-weight cycles. The above step guarantees

    // shortest distances if graph doesn't contain negative weight cycle.

    // If we get a shorter path, then there is a cycle.

    for (int i = 0; i < E; i++)

    {

        int u = graph->edge[i].src;

        int v = graph->edge[i].dest;

        int weight = graph->edge[i].weight;

        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])

            printf("Graph contains negative weight cycle");

    }

    printArr(dist, V);

    return;

}

// Driver program to test above functions

int main()

{

    /* Let us create the graph given in above example */

    int V = 5; // Number of vertices in graph

    int E = 8; // Number of edges in graph

    struct Graph* graph = createGraph(V, E);

    // add edge 0-1 (or A-B in above figure)

    graph->edge[0].src = 0;

    graph->edge[0].dest = 1;

    graph->edge[0].weight = -1;

    // add edge 0-2 (or A-C in above figure)

    graph->edge[1].src = 0;

    graph->edge[1].dest = 2;

    graph->edge[1].weight = 4;

    // add edge 1-2 (or B-C in above figure)

    graph->edge[2].src = 1;

    graph->edge[2].dest = 2;

    graph->edge[2].weight = 3;

    // add edge 1-3 (or B-D in above figure)

    graph->edge[3].src = 1;

    graph->edge[3].dest = 3;

    graph->edge[3].weight = 2;

    // add edge 1-4 (or A-E in above figure)

    graph->edge[4].src = 1;

    graph->edge[4].dest = 4;

    graph->edge[4].weight = 2;

    // add edge 3-2 (or D-C in above figure)

    graph->edge[5].src = 3;

    graph->edge[5].dest = 2;

    graph->edge[5].weight = 5;

    // add edge 3-1 (or D-B in above figure)

    graph->edge[6].src = 3;

    graph->edge[6].dest = 1;

    graph->edge[6].weight = 1;

    // add edge 4-3 (or E-D in above figure)

    graph->edge[7].src = 4;

    graph->edge[7].dest = 3;

    graph->edge[7].weight = -3;

    BellmanFord(graph, 0);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.