Graph problem

[NormalUser1234]

Hello, I'm having a very hard time solving this problem

My work is to read from the text file, apply shortest path searching (BFS or UCS), and print out the shortest path. But what I have done is only read from the file, here is my program:

#include <iostream>
#include <vector>
#include <fstream>

class graph {
private:
    int total, source, goal;
    std::vector<std::vector<int>> g;
public:
    void read_file(const char* name);
};

void graph::read_file(const char* name) {
    std::ifstream fin(name);

    fin >> total >> source >> goal;
    for (int i = 0; i < g.size(); i++) {
        for (int j = 0; j < g[i].size(); j++) {
            fin >> g[i][j];
        }
    }
    fin.close();
}

Until now, I don't know what to do next. Can anyone help me solve this problem? Thank you!

[lastchance]

How about writing int main()? Then you could compile it! And check it.

Then you can start coding one "search" routine at a time.

Why have you called your class "matrix"? - it isn't. g is the matrix. The class is (the rudiments of) a "graph".

[NormalUser1234]

@lastchance
Hello sir, thanks for your reply!

I haven't written the int main() yet because it's for the output, and I don't know how to implement the search algorithm to output the shortest path.

I will change the class into "graph".

[lastchance]

I haven't written the int main() yet

Develop your program incrementally, testing as you go along.

You can't possibly test it if it doesn't compile.

[NormalUser1234]

@lastchance
Hello sir, what should I test in the int main() if I'm stuck at writing the search algorithm, the only thing I can do it's reading from the file and assign those numbers to variables.

[lastchance]

Write an int main();
Instantiate a member of your class.
Get it to read the data.
Write out the matrix to check that it has been read correctly.

Then ... and only then ... start writing your routines to search.

[NormalUser1234]

@lastchance
Hello sir, I have tested my read file function and it works, the output to the console is the same as the text file.

[lastchance]

Good!
And now you can introduce the first function - say
int graph::bfs( int source, int destination )
that will return the shortest path from source to target.

An algorithm that will do it with a queue is explained at
https://cp-algorithms.com/graph/breadth-first-search.html
but there are plenty of other sources. Note that, as your graph is weighted, you may have to run it till all vertices have been considered - not just take the first time that the destination is visited. Are you allowed to use Dijkstra's variant here?

I presume that you will code the same way as you have been taught the algorithm.

[NormalUser1234]

I have modified the program, written the function for BFS, and print out the path between 2 vertices

#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

std::vector<bool> visited;
std::vector<int> p;

void BFS(std::vector<std::vector<int>>& g, int source) {
	int total = g.size();
	visited = std::vector<bool>(total, false);
	
	std::queue<int> q;

	while (!q.empty()) {
		int temp = q.front();
		q.pop();
		for (int i = 0; i < total; i++) {
			if (!visited[i]) {
				visited[i] = true;
				q.push(i);
			}
		}
	}
}

void print_path(int source, int goal) {
	if (p[goal] == source)
		std::cout << source << " " << goal;
	else {
		print_path(source, p[goal]);
		std::cout << " " << goal;
	}
}

int main() {
	std::vector<std::vector<int>> g;
	int total, source, goal;
	std::ifstream fin("matrix.txt");
	fin >> total >> source >> goal;

	g.resize(total);

	for (int i = 0; i < g.size(); i++) {
		for (int j = 0; j < g[i].size(); j++) {
			fin >> g[i][j];
		}
	}
	fin.close();

	BFS(g, source);
	if (visited[goal])
		print_path(source, goal);
}

The output for the program is wrong, any help with this? Thanks!

[lastchance]

Why have you changed your graph class?

Your code isn't making any use of your adjacency matrix g at all - either to decide what is accessible or to use its weights.

What have you been taught in the way of this algorithm? Does Dijkstra's algorithm come under the category of BFS?

[NormalUser1234]

Never mind, I figure it out.