A shortest path algorithm used to find the shortest path between two nodes in a graph. It works by maintaining a priority queue of unvisited nodes and their tentative distances from a source node. Starting from the source node, it visits the neighboring nodes and updates their tentative distances if a shorter path is found. This process is repeated until all nodes have been visited. (Note: It only works for non-negative weights)

Time Complexity: O((n+m)log(n)) with prioirty queues, O(n²) without

            int getMinimumUnvisited(vector<bool> &visited, vector<int> &distances)
              {
              
                  int minimumIndex = 0;
                  int minDistance = INT_MAX;
              
                  for (int i = 0; i < distances.size(); i++)
                  {
                      if (distances.at(i) < minDistance && !visited.at(i))
                      {
                          minimumIndex = i;
                          minDistance = distances.at(i);
                      }
                  }
                  return minimumIndex;
              }
              
              vector<int> dijkstra(vector<vector<int>> &graph, int starting)
              {
              
                  vector<bool> visited;
                  visited.resize(graph.size(), false);
                  vector<int> distances;
                  distances.resize(graph.size(), INT_MAX);
                  distances.at(starting) = 0;
              
                  for (int i = 0; i < graph.size(); i++)
                  {
                      int current = getMinimumUnvisited(visited, distances);
                      visited.at(current) = true;
                      for (int j = 0; j < graph.at(0).size(); j++)
                      {
                          if (graph.at(i).at(j) != 0 && !visited.at(j))
                          {
                              distances.at(j) = min(distances.at(j), distances.at(i) + graph.at(i).at(j));
                          }
                      }
                  }
              
                  return distances;
              }