Dijkstra's Algorithm finding the shortest distance between two vertices c++

Question

I've been working on a program to get some basic knowledge on how path-finding works and decided to use Dijkstra's Algorithm to find the shortest distance between two points of a 2D array which the user chooses. I have used a Graph class with three methods, one for read, print and shortest. However I do not know how to go about making the algorithm for the program I have made. Any help would be appreciated!

The program reads in these values with the first one being set to a variable called size and the rest being input into the 2D array called distance.

4
0     1.7   0.3   0 
1.7   0     0.1   3.6 
0.3   0.1   0     0 
0     3.6   0     0

This is my Graph.h file:

class Graph
{
 public:
  void read(const char* filename);
  void print(ostream& out);
  float shortest(int v1, int v2);
 private:
  int size;
  float max_edge_length;
  float distance[MAX_VERTICES][MAX_VERTICES];
};

Below is my start on creating the read and print methods.

void Graph::read(const char* filename){
    int x, y;
    ifstream myfile(filename);

    if (myfile.good()){
        myfile >> size;
        for (y = 0; y < size; y++){
            for (x = 0; x < size; x++){
                myfile >> distance[x][y];
            }
        }
    }
} 

void Graph::print(ostream& out){

    out << size << endl;
    for (int y = 0; y < size; y++){
        for (int x = 0; x < size; x++){
            out << distance[x][y] << " ";
        }   
        out << endl;
    }
}

float Graph::shortest(int v1, int v2){


}

The second data structure you need for pathfinding (after the graph) is a priority queue. Can you implement an efficient templated priority queue? Can you build one out of existing standard library parts? What if you had to build your own from scratch; how would you do it? — Eric Lippert
Are you asking us to provide a Dijkstra's algorithm implementation for you? This might be a little off-topic, there's loads of C++ tutorials, what sources have you checked before posting here and what have you tried so far to implement it? — Zimano

郭妙友郭妙友 · Accepted Answer · 2017-02-22T09:48:16

if your graph is sure by after read from file and shortest is often use.

you can use Floyd's Algorithm. it's simple than Dijkstra

take O(n^3) (n is your graph point number) build once and query shortest everyTime use O(1)

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

but if your graph's point number large(like 100000). 2D array isn't good at store graph. it's will cost 100000*100000*sizeof(float) memory

your can store graph by side

Dijkstra's Algorithm finding the shortest distance between two vertices c++

1 Answers