Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Gaurav DS Worksheet 4

    Uploaded by

    Hrishabh Gupta
    The document is a worksheet for a student that includes: 1) The aim is to efficiently compute the least-cost path in a directed graph where edge weights are x, 2x, or 3x. 2) The source code defines a graph as a class and generates a sample graph to test path finding between nodes. 3) Screenshots show the output of querying the shortest paths between nodes in the sample graph.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Gaurav DS Worksheet 4

    Uploaded by

    Hrishabh Gupta
    13 views4 pages
    The document is a worksheet for a student that includes: 1) The aim is to efficiently compute the least-cost path in a directed graph where edge weights are x, 2x, or 3x. 2) The source code defines a graph as a class and generates a sample graph to test path finding between nodes. 3) Screenshots show the output of querying the shortest paths between nodes in the sample graph.

    Original Description:

    resume of gaurav

    Original Title

    Gaurav DS worksheet 4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document is a worksheet for a student that includes: 1) The aim is to efficiently compute the least-cost path in a directed graph where edge weights are x, 2x, or 3x. 2) The source code defines a graph as a class and generates a sample graph to test path finding between nodes. 3) Screenshots show the output of querying the shortest paths between nodes in the sample graph.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    13 views4 pages

    Gaurav DS Worksheet 4

    Uploaded by

    Hrishabh Gupta
    The document is a worksheet for a student that includes: 1) The aim is to efficiently compute the least-cost path in a directed graph where edge weights are x, 2x, or 3x. 2) The source code defines a graph as a class and generates a sample graph to test path finding between nodes. 3) Screenshots show the output of querying the shortest paths between nodes in the sample graph.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    DEPARTMENT OF

    COMPUTER SCIENCE & ENGINEERING

    WORKSHEET 4

    Student Name: Hrishabh Gupta UID: 22BCS50102


    Branch: CSE Section/Group: 902/B
    Semester: 3 Date of Performance: Nov 06, 2023
    Subject Name: Data Structures Subject Code: 22CSH-211

    1. Aim: Consider a directed graph where the weight of its edges can be one of x, 2x or
    3x (x is a positive integer). Efficiently compute the least-cost path from source to
    destination.

    2. Source Code:
    #include <iostream>
    using namespace std;
    class graph {
    public:
    graph *e0, *e1 , *e2 , *e3 , *e4;
    int wt0, wt1 , wt2 , wt3 , wt4;
    };
    int main(){
    graph g0,g1,g2,g3,g4;
    g0.e0 = NULL; g0.wt0 = 0;
    g0.e1 = &g1; g0.wt1 = 3;
    g0.e2 = NULL; g0.wt2 = 0;
    g0.e3 = NULL; g0.wt3 = 0;
    g0.e4 = &g4; g0.wt4 = 1;
    g1.e0 = NULL; g1.wt0 = 0;
    g1.e1 = NULL; g1.wt1 = 0;
    g1.e2 = &g2; g1.wt2 = 1;
    g1.e3 = &g3; g1.wt3 = 3;
    g1.e4 = &g4; g1.wt4 = 1;
    g2.e0 = NULL; g2.wt0 = 0;
    g2.e1 = NULL; g2.wt1 = 0;
    g2.e4 = NULL; g2.wt4 = 0;
    g2.e3 = NULL; g2.wt3 = 0;
    g2.e2 = NULL; g2.wt2 = 0;
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING

    g3.e0 = NULL; g3.wt0 = 0;


    g3.e1 = NULL; g3.wt1 = 0;
    g3.e2 = NULL; g3.wt2 = 0;
    g3.e3 = NULL; g3.wt3 = 0;
    g3.e4 = NULL; g3.wt4 = 0;
    g4.e0 = NULL; g4.wt0 = 0;
    g4.e1 = NULL; g4.wt1 = 0;
    g4.e2 = &g2; g4.wt2 = 2;
    g4.e3 = &g3; g4.wt3 = 1;
    g4.e4 = NULL; g4.wt4 = 0;
    graph *ptr;
    int source , dest;
    cout<<"enter the source : ";
    cin>>source;
    cout<<"enter the destination : ";
    cin>>dest;
    if(source == 0){
    if(dest == 0){
    cout<<"source and destination are same.";
    }
    else if(dest == 1){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g0.wt1;
    }
    else if(dest == 2){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g0.wt4 +
    g4.wt2;
    }
    else if(dest == 3){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g0.wt4 +
    g4.wt3;
    }
    else if(dest == 4){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g0.wt4;
    }
    }
    else if(source == 1){
    if(dest == 1){
    cout<<"source and destination are same.";
    }
    else if(dest == 0){
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING

    cout<<"no path is present. ";


    }
    else if(dest == 2){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g1.wt2;
    }
    else if(dest == 3){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is :
    "<<g1.wt4+g4.wt3;
    }
    else if(dest == 4){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g1.wt4;
    }
    }
    else if(source == 2){
    cout<<"no path is present. ";
    }
    else if(source == 3){
    cout<<"no path is present. ";
    }
    else if(source == 4){
    if(dest == 1){
    cout<<"no path is present. ";
    }
    else if(dest == 0){
    cout<<"no path is present. ";
    }
    else if(dest == 2){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g4.wt2;
    }
    else if(dest == 3){
    cout<<"least cost path from "<<source<<" to "<<dest<<" is : "<<g4.wt3;
    }
    else if(dest == 4){
    cout<<"source and destination are same.";
    }
    }
    return 0;
    }
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING

    3. Screenshot of Outputs:

    4. Learning Outcomes
    (i) I now understand what a graph in a data structure is.
    (ii) I now know how to use classes to generate graphs.
    (iii) I now understand the idea behind data structures' weighted graphs.
    (iv) I now know how to use a weighted graph to determine the shortest path between two
    nodes.
    (v) I now understand how to traverse a graph's nodes.

    You might also like