Thiết kế website giá rẻ

Question

Code posted below. Basically, a friend and I are working on a C++ project where we’re taking a graph.txt file as an input, and it’s supposed to run Dijkstra’s Shortest Path Algorithm and output the adjacency matrix with the distances from each vertex. We’re given test .txt files, but no matter what I try to do to fix my matrix code, it doesn’t output the correct one. I think there’s some infinite loop going on, but I can’t find where.

Here’s the output that the test file is supposed to yield vs what it actually yields.

Here’s my code:

Graph.cpp:

#include "graph.h"
#include <limits.h>
#include <iostream>

// Constructor to initialize numVertices, minDistance, and adjacencyMatrix
graph::graph(int numVerts) {
    numVertices = numVerts;
    adjacencyMatrix = new int*[numVertices];
    oddVerts = new int[numVertices]; // Allocate memory for oddVertices array

    for (int i = 0; i < numVertices; ++i) {
        adjacencyMatrix[i] = new int[numVertices];
        int rowSum = 0;

        for (int j = 0; j < numVertices; ++j) {
            adjacencyMatrix[i][j] = 0; // Initialize adjacencyMatrix elements to 0
            rowSum += adjacencyMatrix[i][j];
        }
        // Create an array of row sums to represent odd degree vertices
        oddVerts[i] = rowSum;
    }
}

// Destructor definition
graph::~graph() {
    // Deallocate memory for adjacencyMatrix and oddVerts
    for (int i = 0; i < numVertices; ++i) {
        delete[] adjacencyMatrix[i];
    }
    delete[] adjacencyMatrix;
    delete[] oddVerts;
}

// Definition of executeDijkstra function
void graph::executeDijkstra() {
    int* dist = new int[numVertices]; // Allocate memory for distance array
    bool* sptSet = new bool[numVertices]; // Allocate memory for shortest path tree set

    // Initialize distances and shortest path tree sets
    for (int i = 0; i < numVertices; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    // Distance from source to itself is always 0
    dist[0] = 0; // Assuming source vertex is the first vertex

    // Find shortest paths for all vertices
    for (int count = 0; count < numVertices - 1; count++) {
        int u = minDistance(dist, sptSet, numVertices);

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

        // Update distances of the adjacent vertices
        for (int v = 0; v < numVertices; v++)
            if (!sptSet[v] && adjacencyMatrix[u][v] && 
                dist[u] != INT_MAX &&
                dist[u] + adjacencyMatrix[u][v] < dist[v])
                dist[v] = dist[u] + adjacencyMatrix[u][v];
    }

    // Print the shortest distances from source
    std::cout << "Vertex   Distance from Sourcen";
    for (int i = 0; i < numVertices; i++)
        std::cout << "t" << i << "tttt " << dist[i] << std::endl;

    // Free dynamically allocated memory
    delete[] dist;
    delete[] sptSet;
}

// Helper function for finding minimum distance vertex
int graph::minDistance(int dist[], bool sptSet[], int V) {
    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;
}

void graph::printAdjacencyMatrix() {
    // Print column headers
    std::cout << "Adjacency Matrix:nn";
    std::cout << "  ";
    for (int i = 0; i < numVertices; ++i) {
        std::cout << i << " ";
    }
    std::cout << "n";

    // Print row headers and matrix values
    for (int i = 0; i < numVertices; ++i) {
        std::cout << i << " ";
        for (int j = 0; j < numVertices; ++j) {
            std::cout << adjacencyMatrix[i][j] << " ";
        }
        std::cout << "n";
    }
}

void graph::addEdge(int startVertex, int endVertex) {
    // Check if vertices are within the range of the adjacency matrix
    if (startVertex >= 0 && startVertex < numVertices && endVertex >= 0 && endVertex < numVertices) {
        // Adding an edge to the graph by updating the adjacency matrix
        adjacencyMatrix[startVertex][endVertex] = 1; // Assuming it's an unweighted graph
        adjacencyMatrix[endVertex][startVertex] = 1; // Since it's an undirected graph, update the symmetric entry
    } else {
        std::cout << "Vertex indices out of range!" << std::endl;
    }
}


// Implementation of printOddDegreeVertices function
void graph::printOddDegreeVertices() {
    std::cout << "The odd degree vertices in G:n";
    std::cout << "O = { ";
    
    for (int i = 0; i < numVertices - 1; i++) {
        std::cout << oddVerts[i] << " ";
    }
    std::cout << "}" << std::endl;
}

Graph.h:

#ifndef GRAPH_H
#define GRAPH_H

class graph {
private:
    int numVertices;
    int numEdges;
    int** adjacencyMatrix;
    int minDistance(int dist[], bool sptSet[], int V);
    int *oddVerts;

public:
    // Constructor and destructor declarations
    graph(int numVerts);
    ~graph();

    // Function to add an edge to the graph
    void addEdge(int startVertex, int endVertex);

    // Function to print the adjacency matrix
    void printAdjacencyMatrix();

    // Function to find vertices with odd degree
    void printOddDegreeVertices();

    // Function to execute Dijkstra's algorithm
    void executeDijkstra();
};

#endif

Edge.cpp:

#include "Edge.h"

Edge::Edge(){
    this->startVert = -1;
    this->endVert = -1;
    this->weight = -1;
}

Edge::Edge(int start, int end){
    this->startVert = start;
    this->endVert = end;
    this->weight = 1;
}

int Edge::getWeight(){
    return this->weight;
}

void Edge::setWeight(int newWeight){
    this->weight = newWeight;
}

Edge.h:

#ifndef EDGE_H
#define EDGE_H

class Edge{
private:
    int startVert;
    int endVert;
    int weight;
public:
    Edge();
    Edge(int, int);
    int getWeight();
    void setWeight(int);
};


#endif

Vertex.cpp:

#include "Graph.h"
#include "Vertex.h"
#include <limits.h>
#include <iostream> // for std::cout and std::endl


Vertex::Vertex(){
    this->index = -1;
    this->degree = -1;
}

int Vertex::getIndex(){
    return this->index;
}

int Vertex::getDegree(){
    return this->degree;
}

void Vertex::setIndex(int index){
    this->index = index;
}

void Vertex::setDegree(int deg){
    this->degree = deg;
}

Vertex.h:

#ifndef VERTEX_H
#define VERTEX_H

class Vertex{
private:
    int index;
    int degree;
public:
    Vertex();
    int getIndex();
    int getDegree();
    void setIndex(int);
    void setDegree(int);
};


#endif

Main.cpp:

#include "graph.h"
#include <limits.h>
#include <iostream>

int main() { // The manager overseeing everything

    // start of the initial pipeline that loads the test case file stream from std::cin

    int numOfVertices;
    int numOfEdges;

    if (!std::cin.eof()) {
        std::cin >> numOfVertices;
        std::cin >> numOfEdges;
    } else {
        std::cout << "Input not found!" << std::endl;
        return 0;
    }

    graph graph(numOfVertices); // Create a graph object with the given number of vertices

    while (!std::cin.eof()) { // Keep getting stuff until there's nothing left
        int startVertex;
        int endVertex;
        std::cin >> startVertex;
        std::cin >> endVertex;
        graph.addEdge(startVertex, endVertex); // Put the new thing into a container
    }

    graph.printAdjacencyMatrix();

    graph.printOddDegreeVertices();
    
    graph.executeDijkstra();
    
    return 0;
}

Thanks!

I’ve tried initializing the matrix values differently. I’ve double-checked addEdge to make sure the input vertex indices are within the range of the adjacency matrix. I’ve used different test case files just in case it was the one, but I get the same result each time.

Thiết kế website giá rẻ

Danh mục

What could be causing an adjacency matrix to yield an incorrect output?