ZuoTi.Pro
Question

Explain the code and analyze the performance of algorithm #include<stdio.h> #include<string.h> #define NUM 1...

Explain the code and analyze the performance of algorithm

#include<stdio.h>
#include<string.h>

#define NUM 100
#define maxint 10000

void dijkstra(int n,int v,int dist[],int prev[],int c[][NUM])
{
   int i,j;
   bool s[NUM];
   for(i=1; i<=n; i++)
   {
       dist[i] = c[v][i];
       s[i] = false;
       if (dist[i]>maxint) prev[i] = 0;
       else prev[i] = v;
   }
   dist[v] = 0;
   s[v] = true;
   for(i=1; i<n; i++)
   {
       int tmp = maxint;
       int u = v;
       for(j=1; j<=n; j++)
           if(!(s[j]) && (dist[j]<tmp))
           {
               u = j;
               tmp = dist[j];
           }
       s[u] = 1;
       for(j=1; j<=n; j++)
           if(!(s[j]) && c[u][j]<maxint)
           {
               int newdist = dist[u]+c[u][j];
               if (newdist<dist[j])
               {
                   dist[j] = newdist;
                   prev[j] = u;
               }
           }
   }
}

int main()
{
   int m,n;
   while(scanf("%d%d",&n,&m)!=EOF && (m || n))
   {
       int i,j;
       int dist[NUM] = {0};
       int prev[NUM] = {0};
       int c[NUM][NUM];
       memset(c,1,sizeof(c));
       int v,w,edge;
       for(i=0; i<m; i++)
       {
           scanf("%d%d%d",&v,&w,&edge);
           c[v][w] = edge;
       }
       dijkstra(n,1,dist,prev,c);
       for(i=2; i<=n; i++)
           printf("%d ",dist[i]);
       printf("\n");
       for(j=2; j<=n; j++)
       {
           printf("%d",j);
           int t = prev[j];
           while (t!=1)
           {
               printf("-->%d",t);
               t=prev[t];
           }
           printf("-->1\n");
       }
   }
   return 0;
}

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

This code implements the famous Dijkstra’s shortest path algorithm.

Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSet and has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

The code prints the shortest part of each node from vertex 1.

Time Complexity of the implementation is O(n^2).

0 0
Add a comment
Know the answer?
Add Answer to:
Explain the code and analyze the performance of algorithm #include<stdio.h> #include<string.h> #define NUM 1...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • ​what's wrong with my code?????? #include <stdio.h> #include <stdlib.h> #include <string.h>                         &

    ​what's wrong with my code?????? #include <stdio.h> #include <stdlib.h> #include <string.h>                            #define MAXBINS 99 #define MAXCORS 26 #define MAXCUS 100 #define MAXPUR 10 /* datatype for a list of orders ----------------- */ typedef struct { int bin_order_number; char bin_order_char; }bin_order; typedef struct { int orderNo; bin_order orderbin; }order; typedef struct { int cusnumber; int n;   /* number of the orders what the txt include */ order oo[MAXPUR+1]; }customer; typedef struct{ int n; /*number of the customers */ customer cc[MAXCUS+1];...

  • #include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> int main(void) { /* Type your code here....

    #include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> int main(void) { /* Type your code here. */ int GetNumOfNonWSCharacters(const char usrStr[]) { int length; int i; int count = 0; char c; length=strlen(usrStr); for (i = 0; i < length; i++) { c=usrStr[i]; if ( c!=' ' ) { count++; } }    return count; } int GetNumOfWords(const char usrStr[]) { int counted = 0; // result // state: const char* it = usrStr; int inword = 0; do switch(*it)...

  • Do you have a flowgorithim flow chart for this code? #include <stdio.h> int main() { int num,i=0,sum=0; float aver...

    Do you have a flowgorithim flow chart for this code? #include <stdio.h> int main() { int num,i=0,sum=0; float average; int customerNumbers[num]; int customerSales[num]; printf("How many customers do you want to track?\n"); scanf("%d",&num); while(i<num) { printf("Enter the customer number. "); scanf("%d",&customerNumbers[i]); printf("Enter the sales for the customer "); scanf("%d",&customerSales[i]); i++; } printf("Sales for the Customer"); printf("\nCustomer Customer"); printf("\nNumber Sales"); for(i=0;i<num;i++) { printf("\n %d \t %d",customerNumbers[i], customerSales[i]); sum=sum+customerSales[i]; } average=(int)sum/num; printf("\n Total sales are $%d",sum); printf("\n Average sales are $%.2f",average); printf("\n --------------------------------------------");...

  • #include <stdio.h> #include string.h     #define C17_PRICE 12.80 #define F25_PRICE 4.29 #define DN3_PRICE 10.00 #define GG7_PRICE...

    #include <stdio.h> #include string.h     #define C17_PRICE 12.80 #define F25_PRICE 4.29 #define DN3_PRICE 10.00 #define GG7_PRICE 35.00 #define MV4_PRICE 18.49 #define DISCOUNT        0.05 #define DISC_THRES    10 #define SAME_DAY_DELIVERY =   35.0 #define NEXT_DAY_DELIVERY =   20.0    typedef enum{ WRONG, C17, F25, DN3, GG7, MV4} part     /*--- Function Prototypes ------------*/ part getPartType ( void ); int getquantity ( void ); int getDeliveryOption ( void ); float calcPriceOfParts( part orderedPart, int quantity ); float calcTotalCarges ( float orderPrice, char...

  • Please explain how these code run for each line #include<stdio.h> #include<string.h> /** * Part A */...

    Please explain how these code run for each line #include<stdio.h> #include<string.h> /** * Part A */ struct myWord{    char Word[21];    int Length; }; int tokenizeLine(char line[], struct myWord wordList[]); void printList(struct myWord wordList[], int size); void sortList(struct myWord wordList[], int size); /** * main function */ int main() {    struct myWord wordList[20];    char line[100];    printf("Enter an English Sentence:\n");    gets(line);    int size = tokenizeLine(line, wordList);    printf("\n");    printf("Unsorted word list.\n");    printList(wordList, size);...

  • Explain the following code, line by line. As well as the is going on over all....

    Explain the following code, line by line. As well as the is going on over all. #include <stdio.h> int main() {   int a[30];   int i,j,lasti;   int num;      lasti=0;   // scanf the number   scanf("%d",&a[0]);   while (1)   {   // sacnf the new number   printf("Enter another Number \n");   scanf("%d",&num);   for(i=0;i<=lasti;i=i+1)   {   printf("%d \n",a[i]);   // we check if the num that we eneterd is greter than i   if(a[i] > num)   {   for(j=lasti; j>= i;j--)   {   a[j+1]=a[j];   }      a[i]=num;   lasti++;   break;   }   }...

  • ​what is the output? Consider the following program: #include <stdio.h> #include <stdlib.h> #define size 3 void...

    ​what is the output? Consider the following program: #include <stdio.h> #include <stdlib.h> #define size 3 void func(int **a) {int tmp; for (int i = 0; i < size; i++) {for (int j = i; j < size, j++) {tmp = *(*(a+i)+j); *(*(a+i)+j) = *(*(a+j)+i); *(*(a+j)+i) = tmp;}}} int main() {int **arr = malloc(sizeof(int*) * size); for(int i = 0; i < size; i++) {arr[i] = malloc(sizeof(int) * size); for (int j = 0; j < size, j++) arr[i][j] = 2*i...

  • Can you write the algorithm for this code? #include<stdio.h> int main() { int process[20], priority[20], arrival_time[20],...

    Can you write the algorithm for this code? #include<stdio.h> int main() { int process[20], priority[20], arrival_time[20], burst_time[20], turnaround_time[20], waiting_time[20]; int i, j, limit, sum = 0, position, temp; float average_wait_time, average_turnaround_time; printf("Enter Total Number of Processes:\t"); scanf("%d", &limit); printf("\nEnter Burst Time and Priority For %d Processes\n", limit); for(i = 0; i < limit; i++) { printf("\nProcess[%d]\n", i + 1); printf("Process Burst Time:\t"); scanf("%d", &burst_time[i]); printf("Process Priority:\t"); scanf("%d", &priority[i]); process[i] = i + 1; } for(i = 0; i < limit;...

  • Finish function to complete code. #include <stdio.h> #include <stdlib.h> #include<string.h> #define Max_Size 20 void push(char S[],...

    Finish function to complete code. #include <stdio.h> #include <stdlib.h> #include<string.h> #define Max_Size 20 void push(char S[], int *p_top, char value); char pop(char S[], int *p_top); void printCurrentStack(char S[], int *p_top); int validation(char infix[], char S[], int *p_top); char *infix2postfix(char infix[], char postfix[], char S[], int *p_top); int precedence(char symbol); int main() { // int choice; int top1=0; //top for S1 stack int top2=0; //top for S2 stack int *p_top1=&top1; int *p_top2=&top2; char infix[]="(2+3)*(4-3)"; //Stores infix string int n=strlen(infix); //length of...

  • can u please solve it in c++ format,,,, general format which is #include<stdio.h> .......printf and scanf...

    can u please solve it in c++ format,,,, general format which is #include<stdio.h> .......printf and scanf format dont worry about the answers i have down Q3, What is the output of the program shown below and explain why. #include #include <stdio.h> <string.h> int main(void) ( char str[ 39764 int N strlen(str) int nunj for (int i-0; i t Nǐ.de+ printf(") num (str[] 'e); I/ digits range in the ASCII code is 48-57 if (nue > e) f 9 printf( Xdin,...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT