Question

In: Computer Science

i need to find complexity and cost and runtime for each line of the following c++...

i need to find complexity and cost and runtime for each line of the following c++ code :

// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <limits.h>
#include <stdio.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
   // Initialize min value
   int min = INT_MAX, min_index;

   for (int v = 0; v < V; v++)
       if (sptSet[v] == false && dist[v] <= min)
           min = dist[v], min_index = v;

   return min_index;
}

// A utility function to print the constructed distance array
void printSolution(int dist[])
{
   printf("Vertex \t\t Distance from Source\n");
   for (int i = 0; i < V; i++)
       printf("%d \t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
   int dist[V]; // The output array. dist[i] will hold the shortest
   // distance from src to i

   bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
   // path tree or shortest distance from src to i is finalized

   // Initialize all distances as INFINITE and stpSet[] as false
   for (int i = 0; i < V; i++)
       dist[i] = INT_MAX, sptSet[i] = false;

   // Distance of source vertex from itself is always 0
   dist[src] = 0;

   // Find shortest path for all vertices
   for (int count = 0; count < V - 1; count++) {
       // Pick the minimum distance vertex from the set of vertices not
       // yet processed. u is always equal to src in the first iteration.
       int u = minDistance(dist, sptSet);

       // Mark the picked vertex as processed
       sptSet[u] = true;

       // Update dist value of the adjacent vertices of the picked vertex.
       for (int v = 0; v < V; v++)

           // Update dist[v] only if is not in sptSet, there is an edge from
           // u to v, and total weight of path from src to v through u is
           // smaller than current value of dist[v]
           if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
               && dist[u] + graph[u][v] < dist[v])
               dist[v] = dist[u] + graph[u][v];
   }

   // print the constructed distance array
   printSolution(dist);
}



Solutions

Expert Solution

#include <limits.h>
#include <stdio.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
//complexity is O(V)
//max of V elements accessed , so o(v) as v operation will b performed so o(v)
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

// A utility function to print the constructed distance array
// complexity is o(V) as each element is accessed only once and total of V elements are accessed or its O(V)
void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
//complexity will be O(V) *[ O(V) + O(V) ] = O(V) /(as O(V) + O(V) = O(V))
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false; // complexity to initailize each element is O(1) , so we need to initalize V element its will be o(V)

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
  
for (int count = 0; count < V - 1; count++) { //total of V element accessed so o(v)
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in the first iteration.
int u = minDistance(dist, sptSet); //complexity to calculate minDistance is o(V) as discussed above.

// Mark the picked vertex as processed
sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++) //total of V elements accessed so its o(v)

// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist);
}


Related Solutions

Can I get a breakdown line by line of the time complexity, I know it is...
Can I get a breakdown line by line of the time complexity, I know it is O(NlogN) but I am trying to better understand time complexity as a whole. Input :- N , Array[N]                                function findSmallestPair()                                sort the Array                                int minimumDiff := INFINITY , A := -1 , B := -1;                                  for(int i : 1 to N-1)                                begin for                currentDiff = Array[i]-Array[i-1]                if(currentDiff < minimumDiff)                begin if   ...
I need to write a program in C with the following specification * ​​​​​​​Line one of...
I need to write a program in C with the following specification * ​​​​​​​Line one of the standard input will have the total number of people which must not be greater than 10 * Each of the subsequent lines of input will be the first name of a person and their number (ex. "Adam 85") one space between name and number * Each name must be a maximum of 14 characters * Put the first names into an array called...
Find the Asymptotic time complexity for each of the functions in the following: #Q2 # to...
Find the Asymptotic time complexity for each of the functions in the following: #Q2 # to denote ayymptotic time complexity use the following notation # O(l) O(m) O(a) O(b) # e.g. traversing through l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is O(l) #1 def merge(): l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] m = [15, 16, 17, 18] lm = [] for l_i in l: lm.append(l_i) for m_i in m:...
The following functions have been calculated as the runtime complexity of various algorithms. Identify the Big-O...
The following functions have been calculated as the runtime complexity of various algorithms. Identify the Big-O complexity, and provide witness values to support your answer. Clearly highlight your answer and show any working out you do. i. f(n) = 13 + 3n2 – 9n ii. f(n) = 3n.log2n + 7n iii. f(n) = nn + 2n5 – 7 iv. f(n) = 2log2n + 4n v. f(n) = 20 + 2n4 – n2 +n vi. f(n) = 7n3/4 +3n
Need the correct line of code for c program to solve  this equation . i is a...
Need the correct line of code for c program to solve  this equation . i is a value that the program all ready calculates from user imput. t i = (x*1000)+(y*500)+(z*250
Hello! *Need in C language also need full documentation/explanation of each line* Designing and implementing an...
Hello! *Need in C language also need full documentation/explanation of each line* Designing and implementing an Array of Structures - Course Grade Write a program that uses a structure to store the following data: Member Name Description Name Student name Idnum Student ID number Scores [NUM_TESTS] an array of test scores Average Average test score Grade Course grade Declare a global const directly above the struct declaration
const int NUM_TESTS = 4; //a global constant The program should ask the...
I need to write a c/c++ code to find the maximum sum in those possible combinations...
I need to write a c/c++ code to find the maximum sum in those possible combinations of arrays. There are N arrays with S elements. ex2: 4 arrays with 3 elements.We want to find the greater number in the same column of two arrays(may possible be three or four...arrays), and sum those greater number to find the greatest sum in all of the combinations in those 4 arrays, like: A: [50, 60, 70] B: [80, 40, 20] C: [30, 100,...
*Need in C language also need full documentation/explanation of each line* Thank you! Write a program...
*Need in C language also need full documentation/explanation of each line* Thank you! Write a program that records high-score data from a simulated FIFA soccer game available online. The program will ask the user to enter the number of scores, create two dynamic arrays sized accordingly, ask the user to enter the indicated number of names and scores, and then print the names and scores sorted by score in descending order. The output from your program should look exactly like...
Find the linear regression line for the following table of values. You will need to use...
Find the linear regression line for the following table of values. You will need to use a calculator, spreadsheet, or statistical software. Enter your answer in the form y=mx+b, with m and b both rounded to two decimal places. x y 3 6.03 4 9.65 5 11.49 6 11.57 7 12.96 8 14.97 9 16.31 10 17.43 11 18.55
For the following program segments, write a program that shows the estimated runtime for each piece....
For the following program segments, write a program that shows the estimated runtime for each piece. Run it on your computer when n=1, 10, 100, 1000, 10000, 100000, 1000000 for ten times each so that you can observe the differences in performance among these segments. Segment1:        for (sum=0, i=1; i<=n; i++)                         sum = sum + i; Segment2:        for (sum=0, i=1; i<=n; i++)                                                 for (j=1; j<=i; j++)                                                             sum++; Segment3:        sum= n * (n+1)/2
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT