Given a graph and a starting vertex, count the number of nodes a specified distance away.
Requirements:
Create a graph of int's. Given a starting node with value key and a distance dist , return the number of nodes that have a path from id with exactly dist edges. If there are multiple paths, only consider the shortest one.
int countNodesWithDist(int id, int dist); // example declaration
Examples:
For the graph below, countNodesWithDist(2, 1) should return 2 since there are two nodes 1 step away from 2 (i.e. 4 and 5).
countNodesWithDist(3, 2) should return 2 since there are two nodes 2 steps away from 3 (i.e. 2 and 4).
Write a main function that creates a graph and demonstrates the method above. Make sure your graph covers as many edge case scenarios as you can think of and call the method with multiple combinations of starting vertex and distance to show that it works in all cases, and print out the results.
Code:
/*We can make use of standard Dijikstra's algorithm here
, although the graph is not weighted but
we could assign weight of 1 to every edge and store the distance of
each vertex from the source
and the compare the distances which are equal to
distance.
We are using the adjacency listr representation of the graph here
Time Complexity - O(ElogV) where E is number of edges
and V are the number of vertices.
*/
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
vector<pair<int,int> > adj[101];
int dis[101]; // dis array to store the distances from source
bool vis[101]; // vis array to keep track of visited vertices
int vertices,edges;
struct comp
{
bool operator()(pair<int,int> &a, pair<int,int>
&b)
{
return a.second > b.second;
}
};
priority_queue<pair<int,int>, vector<pair<int,int> > , comp> pq;
int countNodeWithDistance(int source,int
distance){
int i, u, v, w, sz;
for (i = 1; i <= vertices; i++)
dis[i] = 1<<20;
dis[source] = 0;
pq.push({source, 0});
// standard dijikstra algorithm using priority
queue
while (!pq.empty())
{
u = pq.top().first;
pq.pop();
if (vis[u])
continue;
sz = adj[u].size();
for (i = 0; i < sz; i++)
{
v = adj[u][i].first; //vertex
w = adj[u][i].second; // cost
// comparing the distance for current node from source if its not
visited yet
//If its lesser than already computed distance than we will update
it with new value
//You could replace w with 1 since the weight is 1 only
in each case
if (!vis[v] && dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
pq.push({v, dis[v]});
}
}
vis[u] = 1;
}
int count=0;
for (int j = 1; j <= vertices; j++)
{
if(dis[j]==distance){
count++;
cout<<"Node "<<j<<" at distance
"<<dis[j]<<"\n";
}
}
return count;
}
int main()
{
// take vertices, edges and source as input
int i, u, v, w, sz, source,distance;
cin >> vertices >> edges;
for (i = 0; i < edges; i++)
{
cin >> u >> v;
adj[u].push_back({v, 1});
adj[v].push_back({u, 1});
}
cin >> source>>distance;
cout<<"Nodes at distance
"<<distance<<" from source "<<source<<" are
: "
<<countNodeWithDistance(source,distance);
return 0;
}
Input:
Output:
Given a graph and a starting vertex, count the number of nodes a specified distance away....
Given a graph and a starting vertex, count the number of nodes a specified distance away. C++ Programming
You're running Dijkstra's algorithm to find all shortest paths starting with vertex A in the graph below, but you pause after vertex E has been added to the solution (and the relaxation step for vertex E has been performed). Annotate the graph as follows: (1) label each node with its current dist value, (2) darken the edges that are part of the current spanning tree (i.e., the parent links), (3) draw a dotted circle around the "cloud'' of vertices that...
Using the following graph and Dijkstra's algorithm, calculate the shortest distance to each other vertex starting from vertex A. Label all vertices with the total distance (from A). Indicate the order nodes are added to cloud. Draw a Minimum Spanning Tree for the graph. You should label all nodes in the tree, but you do not need to indicate edge weights or total distance. 2 D C L 7 6 2 7 2 A K B 4 7 4 1...
Algorithm Question 5. Below is a graph with edge lengths. Apply Dijkstra's algorithm to find the shortest paths, starting at vertex A, to all other vertices. Write down the sequence in which the edges are chosen, breaking ties by using vertices at the same length in alphabetic orde. 3 Ga 2 5. Below is a graph with edge lengths. Apply Dijkstra's algorithm to find the shortest paths, starting at vertex A, to all other vertices. Write down the sequence in...
for this graph starting at vertex H. Ties should be resolved by whichever vertex is alphabetically earlier. list the order the vertices are removed during Dijkstra's algorithm for this graph starting at vertex H. Also list any update to the known distance values for neighboring vertices (including the initial update from infinity to a known value). Also include a list of edges (pairs of vertices) in the tree that is formed as part of the traversal in Dijkstra's algorithm. Ties...
Solve (a) and (b) using BFS and DFS diagram BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS BFS Given an undirected graph...
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS BFS Given an undirected graph below (a) Show the shortest distance to each vertex...
Please follow all the instructions and do all the parts (a-d)! Create a Java program which implements Dijkstra’s shortest path algorithm according to the psueudocode below. Base the design on the weighted graph implementation used in Problem3.java (provided at the bottom). Your program should include the following features: a. A new method receives a starting vertex index and a target vertex index (e.g. 0 and 4). It computes the shortest distances to all vertexes using Dijkstra’s algorithm. The pseudocode is...
discrete 2 question 31 For Esercises 25.28, write the nodes in a breadth first search of the graph for Exercises 21 the node specified 25、 26, g 20. In the computer network in the accompanying figure, the same message is to be broade Dribe ( 21-24 28. e 27. to nodes 4.Е. F and G. One way to do this is to find the shortest path from C to send out multiple copies of the same message. A more etficient...
Below is the Graph file that needs to be modified(using Python3) : #!/usr/bin/python3 # Simple Vertex class class Vertex: """ Lightweight vertex structure for a graph. Vertices can have the following labels: UNEXPLORED VISITED Assuming the element of a vertex is string type """ __slots__ = '_element', '_label' def __init__(self, element, label="UNEXPLORED"): """ Constructor. """ self._element = element self._label = label def element(self): """ Return element associated with this vertex. """ return self._element def getLabel(self): """ Get label assigned to...