We are given a weighted graph G = (V, E) with weights given by W. The nodes repr

Question

We are given a weighted graph G = (V, E) with weights given by W. The nodes represent cities and the edges are (positive) distances between the cities. We want to get a car that can travel between any two cities: it can leave with a full tank of gas, but cannot purchase gas until it reached its destination. The zero-stop-capacity of the car we purchase is defined to be the longest distance between any two cities that we may travel (but of course, between any two cities we would take the shortest path). A simple way to compute this is to run Floyd-War shall (0(n^3)), and then look at all pairs of vertices/cities and return the greatest distance (0(n^2)). A bit more formally, Floyd-War shall returns W*, where W*[u, v] is the length of the shortest route from city u to v. The zero-stop-capacity is thus max {W*[u, v] | u, v element E}. Now suppose that you want to calculate the necessary one-stop-capacity of a potential car: we are allowed to stop at just one intermediate city to purchase gas for the car. Describe an algorithm to determine what capacity would be needed for our car to travel between any two cities with at most one refueling stop.

Explanation / Answer

// in this program longest path is found by topologically ordering the input graph

// A C++ program to find single source longest distances in a DAG

#include <iostream>

#include <list>

#include <stack>

#include <limits.h>

#define NINF INT_MIN

using namespace std;

#inc

// Graph is represented using adjacency list. Every node of adjacency list

// contains vertex number of the vertex to which edge connects. It also

// contains weight of the edge

class AdjListNode

{

    int v;

    int weight;

public:

    AdjListNode(int _v, int _w) { v = _v; weight = _w;}

    int getV()       { return v; }

    int getWeight() { return weight; }

};

// Class to represent a graph using adjacency list representation

class Graph

{

    int V;    // No. of vertices'

    // Pointer to an array containing adjacency lists

    list<AdjListNode> *adj;

    // A function used by longestPath

    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);

public:

    Graph(int V);   // Constructor

    // function to add an edge to graph

    void addEdge(int u, int v, int weight);

    // Finds longest distances from given source vertex

    void longestPath(int s);

};

Graph::Graph(int V) // Constructor

{

    this->V = V;

    adj = new list<AdjListNode>[V];

}

void Graph::addEdge(int u, int v, int weight)

{

    AdjListNode node(v, weight);

    adj[u].push_back(node); // Add v to u's list

}

// A recursive function used by longestPath.

void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)

{

    // Mark the current node as visited

    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex

    list<AdjListNode>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

    {

        AdjListNode node = *i;

        if (!visited[node.getV()])

            topologicalSortUtil(node.getV(), visited, Stack);

    }

    // Push current vertex to stack which stores topological sort

    Stack.push(v);

}

// The function to find longest distances from a given vertex. It uses

// recursive topologicalSortUtil() to get topological sorting.

void Graph::longestPath(int s)

{

    stack<int> Stack;

    int dist[V];

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

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

        visited[i] = false;

    // Call the recursive helper function to store Topological Sort

    // starting from all vertices one by one

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

        if (visited[i] == false)

            topologicalSortUtil(i, visited, Stack);

    // Initialize distances to all vertices as infinite and distance to source as 0

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

        dist[i] = NINF;

    dist[s] = 0;

    // Process vertices in topological order

    while (Stack.empty() == false)

    {

        // Get the next vertex from topological order

        int u = Stack.top();

        Stack.pop();

        // Update distances of all adjacent vertices

        list<AdjListNode>::iterator i;

        if (dist[u] != NINF)

        {

          for (i = adj[u].begin(); i != adj[u].end(); ++i)

             if (dist[i->getV()] < dist[u] + i->getWeight())

                dist[i->getV()] = dist[u] + i->getWeight();

        }

    }

    // Print the calculated longest distances

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

        (dist[i] == NINF)? cout << "INF ": cout << dist[i] << " ";

}

// Driver program to test above functions

int main()

{

    // Create a graph given in the above diagram. Here vertex numbers are

    // 0, 1, 2, 3, 4, 5 with following mappings:

    // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z

    Graph g(6);

    g.addEdge(0, 1, 5);

    g.addEdge(0, 2, 3);

    g.addEdge(1, 3, 6);

    g.addEdge(1, 2, 2);

    g.addEdge(2, 4, 4);

    g.addEdge(2, 5, 2);

    g.addEdge(2, 3, 7);

    g.addEdge(3, 5, 1);

    g.addEdge(3, 4, -1);

    g.addEdge(4, 5, -2);

    int s = 1;

    cout << "Following are longest distances from source vertex " << s <<" ";

    g.longestPath(s);

    return 0;

}

Output:

Following are longest distances from source vertex 1
INF 0 2 9 8 10

//here output is wrt source 1 that is from source

1 to 1 is 0

1 to 2 is 2

1 to 3 is 9

1 to 4 is 8

1 to 5 is 10

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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