c++ programing question25: Shortest Path Tree Time Limit: 1 seconds Problem Desc
ID: 3903608 • Letter: C
Question
c++ programing question25:
Shortest Path Tree
Time Limit: 1 seconds
Problem Description
Given a graph with positive edge weight and a source s, find a spanning tree such that the the
d_T(s,v)=d(s,v) for each vertex v and the total tree edge weight is minimized.
Total weight of the tree.
d_T(s,v) is the distance from s to v on T, and d(s,v) is the distance on the original graph
Input File Format
There will be a positive integer T at the beginning, which means that there will be T input data.
The first line of input data has three positive integers n, m, and q, representing n points and m edges on the graph, 2 ? n ? 10000, 1 ? m
? 500000, each point is numbered 0 ~ n-1, q is the number of queries.
The next m rows each have three positive integers u, v, and w, which represent an edge from u to v with a weight w, 0 < w <1000.
Then there will be q rows, each with an integer r, representing that a shortest path tree is generated at point r and the weights of all the edges of the tree are summed.
The shortest path tree may not be unique, so must select the one that has the smallest sum of edges' weight.
Output Format
for each input data output q answers, each answer in independent line.
Example Sample Input Sample Output 18 0 16 4 453 0 110 02 3 0 3 20 20 1 23 5 0 57 1 011 022 0 3 2 042 12 1 13 1 141Explanation / Answer
//program to find single source shortest paths
#include<iostream>
#include <list>
#include <stack>
#include <limits.h>
#define INF INT_MAX
using namespace std;
// 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 shortestPath
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 shortest paths from given source vertex
void shortestPath(int s);
};
Graph::Graph(int V)
{
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 shortestPath. See below link for details
// https://www.geeksforgeeks.org/topological-sorting/
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 shortest paths from given vertex. It uses recursive
// topologicalSortUtil() to get topological sorting of given graph.
void Graph::shortestPath(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] = INF;
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] != INF)
{
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 shortest distances
for (int i = 0; i < V; i++)
(dist[i] == INF)? cout << "INF ": cout << dist[i] << " ";
}
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = {{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}
};
dijkstra(graph, 0);
return 0;
}
Minimized weight:
Shortest path with minimized Weight:
// Program to shortest path from a given source vertex ‘s’ to
// a given destination vertex ‘t’. Expected time complexity
// is O(V+E).
#include<bits/stdc++.h>
using namespace std;
// This class represents a directed graph using adjacency
// list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w, int weight); // adds an edge
// finds shortest path from source vertex ‘s’ to
// destination vertex ‘d’.
int findShortestPath(int s, int d);
// print shortest path from a source vertex ‘s’ to
// destination vertex ‘d’.
int printShortestPath(int parent[], int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[2*V];
}
void Graph::addEdge(int v, int w, int weight)
{
// split all edges of weight 2 into two
// edges of weight 1 each. The intermediate
// vertex number is maximum vertex number + 1,
// that is V.
if (weight==2)
{
adj[v].push_back(v+V);
adj[v+V].push_back(w);
}
else // Weight is 1
adj[v].push_back(w); // Add w to v’s list.
}
// To print the shortest path stored in parent[]
int Graph::printShortestPath(int parent[], int s, int d)
{
static int level = 0;
// If we reached root of shortest path tree
if (parent[s] == -1)
{
cout << "Shortest Path between " << s << " and "
<< d << " is " << s << " ";
return level;
}
printShortestPath(parent, parent[s], d);
level++;
if (s < V)
cout << s << " ";
return level;
}
// This function mainly does BFS and prints the
// shortest path from src to dest. It is assumed
// that weight of every edge is 1
int Graph::findShortestPath(int src, int dest)
{
// Mark all the vertices as not visited
bool *visited = new bool[2*V];
int *parent = new int[2*V];
// Initialize parent[] and visited[]
for (int i = 0; i < 2*V; i++)
{
visited[i] = false;
parent[i] = -1;
}
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[src] = true;
queue.push_back(src);
// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while (!queue.empty())
{
// Dequeue a vertex from queue and print it
int s = queue.front();
if (s == dest)
return printShortestPath(parent, s, dest);
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
parent[*i] = s;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.