Please help me with these C++ program questions

[xy06]

Write C++ program to create directed-weighted-graph data structure using adjacency list (use link-list). Insert 1000 vertexes, use random function to insert edge direction and weight.
a. Case-A: Sparse graph, insert 200 x 200 weighted edges
b. Case-B: Dense Graph, insert 700 x 700 weighted edges
c. Case-C: Complete graph, insert 1000 x 1000 weighted edges
d. Test each Case- A, B, and C by counting the total number of edges, and print the correct total edges from above cases, separately.

To extend above Task 2, write C++ program (functions) for graph shortest path algorithms. Implement Dijkstra and Bellman–Ford algorithms. Do comparative analysis of both algorithms by using Task 2.
a. For analysis of each Case- A, B, and C, you need to compute the total time (seconds) consumed by each algorithm. Use time.h to calculate the time.
b. In each Case- A, B, and C, search all possible paths for each vertex to all other vertexes from graph.
c. You should compare both algorithms for each Case- A, B, and C, separately.

Thank you so much!!!

[doug4]

That sounds like a fairly involved homework assignment.

Do you have any specific questions about it?

What do you have so far?

[xy06]

Unfortunately, no. There was just these 2 questions uploaded by the lecturer.

[dhayden]

The hard part is just setting up the data. Here's one example of how to do it.
- A Graph has a vector of Nodes.
- Each Node has an ID (it's position in graph's vector of Nodes), and a list of edges.
- Each edge has the id's of the source and destination node, and weight of the edge:

struct Edge {
    Edge(int s, int d, int w) :
        src(s), dst(d), weight(w) {}
    int src, dst;               // Node id's of src & dst nodes
    int weight;
};

class Node {
public:
    Node(int id_) : id(id_) {}
    int id;
    list<Edge> edges;

    // Insert a new edge if one doesn't exist already.
    // Returns true if the edge was inserted, false if it exists already.
    bool addEdge(int dstID, int weight);
};

class Graph {
public:
    vector<Node> nodes;
    Graph(int N);
    void print(ostream &o);
};

I added Node::addEdge() and Graph::print() for convenience.

Notice that my addEdge() method checks if the edge exists already. This would be expensive for parts b and c where you have lots of edges. So you may want to relax that requirement and do something in the calling code to ensure that you don't have duplicate edges.

[xy06]

Thank you so much!!!!! Appreciate it.