Graph for pathfinding.cpp

1. Creating the graph

The function Init_G creates the graph in an adjency list.

void Init_G() {
    
        for (int i = 0; i < TG; i++) {
            Sommet* s = new Sommet();
            s->num = i;
            s->mark = false;
            G.push_back(s);
        }
    
        for (int i = 0; i < TG; i++) {
            RS[i] = -1;
        }
        
        //1 2 5
        G[0]->voisin.push_back(G[1]);
        G[0]->voisin.push_back(G[2]);
        G[0]->voisin.push_back(G[5]);
        P[0][1] = 7;
        P[0][2] = 9;
        P[0][5] = 14;
    
        // 0 2 3
        G[1]->voisin.push_back(G[0]);
        G[1]->voisin.push_back(G[2]);
        G[1]->voisin.push_back(G[3]);
        P[1][0] = 7;
        P[1][2] = 10;
        P[1][3] = 15;
    
        // 0 1 3 5
        G[2]->voisin.push_back(G[0]);
        G[2]->voisin.push_back(G[1]);
        G[2]->voisin.push_back(G[3]);
        G[2]->voisin.push_back(G[5]);
        P[2][0] = 9;
        P[2][1] = 10;
        P[2][3] = 11;
        P[2][5] = 2;
    
        //  1 2 4
        G[3]->voisin.push_back(G[1]);
        G[3]->voisin.push_back(G[2]);
        G[3]->voisin.push_back(G[4]);
        P[3][1] = 15;
        P[3][2] = 11;
        P[3][4] = 6;
    
        //  3 5
        G[4]->voisin.push_back(G[3]);
        G[4]->voisin.push_back(G[5]);
        P[4][3] = 6;
        P[4][5] = 9;
      
        //  0 2 4
        G[5]->voisin.push_back(G[0]);
        G[5]->voisin.push_back(G[2]);
        G[5]->voisin.push_back(G[4]);
        P[5][0] = 14;
        P[5][2] = 2;
        P[5][4] = 9;
    
        SG[0][0] = 0;
        S_depart = 0;
        S_fin = 4;
    
    }

2. Pathfinding (Djikstra) [in The Main function]

This the for loop in the main function who updates the shortest path.

 for (int i = 0; i < G[sommet]->voisin.size(); i++) {
                
                if ((G[sommet]->voisin[i]->num == S_fin) && (distance == 0)) {
                    R = S_fin;
                    SG2[I][G[sommet]->voisin[i]->num] = sommet;
                   
                    break;
                }
                else if (!G[sommet]->voisin[i]->mark) {
                    if (SG[I][G[sommet]->voisin[i]->num] == -1) {
                   
                       SG[I][G[sommet]->voisin[i]->num] = P[G[sommet]->num][G[sommet]->voisin[i]->num]+ SG[I-1][G[sommet]->num];
                       SG2[I][G[sommet]->voisin[i]->num] = sommet;
                    }
                    else {
                        if ((P[G[sommet]->num][G[sommet]->voisin[i]->num] + SG[I - 1][G[sommet]->num]) <
                            SG[I][G[sommet]->voisin[i]->num]) {
                            SG[I][G[sommet]->voisin[i]->num] = P[G[sommet]->num][G[sommet]->voisin[i]->num] + SG[I - 1][G[sommet]->num];
                            SG2[I][G[sommet]->voisin[i]->num] = sommet;
                            
                        }
    
                    }
    
                    if (SG[I][G[sommet]->voisin[i]->num] < min) {
                        min = SG[I][G[sommet]->voisin[i]->num];
                        R = G[sommet]->voisin[i]->num;
                    }
    
                }
                
                
    
            }