Question

Hi there. I tried to submit this before, but the copy/paste didn't copy my vectors correctly. Hello there. I am trying to implement the djikstras shortest path algorithm into my code in C++ with a vector of vectors. However, when I test I get an error "Exception thrown at 0x75FFC762 in graphMain.exe: Microsoft C++ exception: std::out_of_range at memory location 0x009CF26C" for line 115 in graph.cpp. Could you help me debug? I am so close!

----------------------------FILE NAME: pch.h---------------------------------------
// pch.cpp: source file corresponding to pre-compiled header; necessary for compilation to succeed

#include "pch.h"

// In general, ignore this file, but keep it around if you are using pre-compiled headers.

---------------------------FILE NAME: graph.h---------------------------------------
#include "pch.h"
#include <vector>

using std::vector;
using std::string;

struct Edge
{
   int dest, weight = 0;
  
};
class chart
{
public:
   //the adjacency list
   vector <vector<Edge*>*> list;
  
   chart();
   void addNode();
   void addPath(int source, int dest, int weight);
   void printGraph();
   int minDist(vector <int> distance, vector <bool> visited);
   void dijkstra(vector <vector<Edge*>*> list, int source);
   void printPath(vector <int> distance, int size);
};

-------------------------------FILE NAME: graph.cpp-------------------------------
#include "pch.h"
#include <iostream>
#include "graph.h"
#include <vector>

using std::cout;
using std::endl;
using std::vector;

chart::chart()
{
  
}

void chart::addNode()
{
   //creating a new node and adding it to the 2D Vector of edges
   vector <Edge*> *edges = new vector<Edge *>;
   list.push_back(edges);
}

void chart::addPath(int source, int dest, int weight)
{
   //creating the edge
   Edge *edge = new Edge;
   //filling the edge with a destination and weight
   edge->dest = dest;
   edge->weight = weight;
   //adding an edge to the graph
  
   for (unsigned int i = 0; i < list.size(); ++i)
   {
       //goes back to the main menu if the user tries to add to a location that doesnt exist
       if (source > list.size() - 1 || dest > list.size() - 1 || source < 0)
       {
           cout << "The graph isn't that big yet!" << endl;
           return;
       }
   }
  

  
   //list.at(source)->resize(1);
   //trying to push into the inner vector using the location input by the user
   list.at(source)->push_back(edge);
   //list.at(source)->at(0)->dest = dest;
   //list.at(source)->at(0)->weight = weight;
}

void chart::printGraph()
{
   int count = 0;
  
   for (unsigned int i = 0; i < list.size(); ++i)
   {
       if (list[i]->size() == 0)
       {
           cout << "Node: " << count << endl;
           cout << "No paths defined." << endl;
           cout << endl;
       }
       else
       {
           for (unsigned int j = 0; j < list[i]->size(); ++j)
           {
               cout << "Node: " << count << endl;
               cout << "Destination: " << list.at(i)->at(j)->dest << endl;
               cout << "Length: " << list.at(i)->at(j)->weight << endl;
               cout << endl;
           }
          
       }
       count++;
   }
}

int chart::minDist(vector <int> distance, vector <bool> visited)
{
   int min = INT_MAX, index = -1;
   for (int i = 0; i < list.size(); i++)
   {
       if (visited[i] == false && distance[i] <= min)
       {
           min = distance[i];
           index = i;
       }
   }
       return index;

}

void chart::dijkstra(vector <vector<Edge*>*> list, int source)
{
   vector <int> distance(list.size()); //holding the distances from source vertex
   vector <bool> visited(list.size()); //holds checked/unchecked paths

   for (int i = 0; i < list.size(); i++)
   {
       distance[i] = INT_MAX;
       visited[i] = false;
   }

   distance[source] = 0;

   for (int i = 0; i < list.size(); i++)
   {
       int u = minDist(distance, visited);
       visited[u] = true;

       for (int j = 0; j < list[i]->size(); ++j)
       {
           if (!visited[j] && list.at(u)->at(j) != 0 && distance[u] != INT_MAX && distance[u] + list.at(u)->at(j)->weight < distance[j])
           {
               distance[j] = distance[u] + list.at(u)->at(j)->weight;
           }
       }
   }
   printPath(distance, list.size());
}

void chart::printPath(vector <int> distance, int size)
{
   cout << "Distance from source to destination is:\n " << endl;
   for (int i = 0; i < size; i++)
   {
       cout << i << "----" << distance[i] << endl;
   }
   cout << endl;
}

------------------------------FILE NAME: graphMain.cpp-----------------------------
// graphMain.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include "pch.h"
#include "graph.h"
#include <iostream>
#include <string>
#include <vector>

using std::endl;
using std::cout;
using std::cin;

void testFunc()
{
   chart g;

   g.addNode();
   g.addNode();
   g.addNode();
   g.addNode();
   g.addNode();

   g.addPath(0, 3, 10);
   g.addPath(0, 1, 3);
   g.addPath(1, 2, 4);
   g.addPath(2, 3, 4);

   cout << "Printing the graph...\n" << endl;
   g.printGraph();

   g.dijkstra(g.list, 0);
   g.dijkstra(g.list, 1);
   g.dijkstra(g.list, 2);
   g.dijkstra(g.list, 3);
   g.dijkstra(g.list, 4);

}

int main()
{
   testFunc();

   chart g;
   int count, choice;
   choice = -1;
   count = 0;
  
  
   while (choice != 5)
   {
       int source, dest;

       cout << "Main menu. Your choices are as follows:" << endl;
       cout << "1. Add a node" << endl;
       cout << "2. Add a path" << endl;
       cout << "3. Print the graph" << endl;
       cout << "4. Find the shortest path" << endl;
       cout << "5. Quit" << endl;
      
       cin >> choice;

       switch (choice)
       {
       case 1:
           g.addNode();
           cout << "You've added node " << count << " to the graph." << endl;
           count++;
           break;
       case 2:
           int length;
           cout << "What do you wanna add? (source, dest, distance)" << endl;
           cout << "Source?" << endl;
           cin >> source;
           cout << "Destination?" << endl;
           cin >> dest;
           cout << "Distance?" << endl;
           cin >> length;
           g.addPath(source, dest, length);
           break;
       case 3:
           cout << "The graph contains: " << endl;
           g.printGraph();
           break;
       case 4:
           cout << "Which node would you like to use as a source?" << endl;
           cin >> source;
           g.dijkstra(g.list, source);
           break;
       case 5:
           return 0;
           break;
       }
          
   }
}

Answer 1

The issue is happening in the following line

if (!visited[j] && list.at(u)->at(j) != 0 && distance[u] != INT_MAX && distance[u] + list.at(u)->at(j)->weight < distance[j])

because the inner vector size is less than the one we are trying to access using at operator.

Attach the Resolved Solution in some time.