Nodes in Dijkstra's algorithm are not being saved

Question

I am having a problem with Dijkstra's algorithm in that I can access the next node in a list I created but I cannot save information to that "next node". The structure I am using is a vector that has nodes saved at each index. I am using the addresses of the vector indexes to gain access of the nodes at that index.

I made the vector with nodes from this example: Linked list with multiple parent and child nodes

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <limits>
#include <algorithm>
#include <queue>
#include <vector>
#define INFINITY 999

using namespace std;

struct node
{

int id;
int edge_weight;
int distance_to_source;
//used for reverse iteration to find the path
int previous;

//pointing to children of parent node and the addresses are stored
//in an array
struct node* next_node_list[3];
struct node* previous_node[3];

};



int Dijkstra(vector<node> sub,int source, int target)
{
//intializing for main while loops
int best_path_weight =0;
int end_of_loops= (sub.size());
int child = 0;

//intializing intial distances to INF to show that 
for(int i=0; i < end_of_loops; i++)
{

sub[i].distance_to_source = INFINITY;

}
//source is set to be 0
sub[source].distance_to_source=0;
//copy of sub for later access 
vector<node> copy = sub;

while(!sub.empty())
{
    cout << sub.size() << endl;

    if(sub[0].distance_to_source == INFINITY)
    {
    cout << "new node distance2source is INF" << endl;
    break;

    }
    for(int j = 0; (j < 1); j++)
    {

        if((sub[source].next_node_list[j] == NULL))
        {
        cout << "null child " <<endl;
        break;
        }

        //nextnode = (sub[0]).next_node_list[j];

        child = (sub[0].distance_to_source) + ((sub[0].next_node_list[j]->edge_weight));


        if((child) < ((sub[0].next_node_list[j])->distance_to_source))
        {

            //this is where my problem lies I beleive
            ((sub[0].next_node_list[j])->distance_to_source) = child;

            //used for a reference to have access to final paths
            copy[((sub[0].next_node_list[j])->id)].distance_to_source = child;

            ((sub[0].next_node_list[j])->previous) = sub[0].id;       
        }


    best_path_weight = copy[target].distance_to_source;

    }

    sub.erase(sub.begin());


}


return best_path_weight;
}



int main() {
vector<node> sub;

// changing size of graph
int number_of_vertices = 3;
int source = 0;
int target = 2;
if(target > number_of_vertices)
cout << "ERROR! target cannot be greater than the number of vertices!" << endl; 

for(int i=0; i < number_of_vertices; i++)
{
    //Push new node onto a vector 
    sub.push_back(node());
    //assigning information to nodes
    sub[i].id = i;
    sub[i].edge_weight = 2*i+1;

    for(int j = 0; j < 3; j++)
    {
        sub[i].next_node_list[j]=NULL;
        sub[i].previous_node[j]=NULL;
    }

}
//node linking declaration
//node 0
sub[0].next_node_list[0]=(&sub[1]);
sub[0].next_node_list[1]=(&sub[2]);

//node 1
sub[1].next_node_list[0]=(&sub[2]);
//sub[1].next_node_list[1]=(&sub[4]);
sub[1].previous_node[0]=(&sub[0]);

//node3
sub[2].previous_node[0]=(&sub[0]);
sub[2].previous_node[1]=(&sub[1]);

cout << "distance "<< Dijkstra(sub, source, target) << endl;

}

Answer 1

You are storing pointers to other nodes in the vector. When you make a copy of it the new nodes still point to the nodes in the original vector. Specifically the pointers you have in next_node_list and previous_node.

If you pass sub by reference it might start working. However, it is generally unsafe to store pointers into dynamic containers. When elements get added and removed from vectors they can move from their original location in memory. If you remove from the front then all the remaining elements get shuffled forward. When using push_back there might not be enough space left so a new allocation might be made and the elements are copied/moved to an entirely new block of memory.

One thing you could try is to use a std::vector<std::shared_ptr<node>> and instead of using raw node pointers in next_node_list and previous_node, make them std::weak_ptr<node>. That will allow you to shuffle the vector around whilst maintaining the integrity of the connections.