Блог

я пытаюсь реализовать минимальный путь Дейкстры с помощью C и объектов.

Пока я думаю, что у меня есть почти вся логика, за исключением того, что мой алгоритм завершается досрочно, т.Е. Не посещает каждый узел.

я думаю, что проблема либо в том, как я заполняю свой посещенный массив, либо в том, как я заполняю свою очередь.

я присоединюсь к коду и базовому файлу ввода. вы должны иметь возможность запустить его, передав имя входного файла в качестве аргумента.

заранее большое спасибо!

 #include <iostream>
#include <fstream>
#include <string>
#include <sstream> 
#include <limits>

using namespace std;

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 100001
class Node
{
public:
  Node() {} /* An empty constructor */

  /* Store the information of an out-going edge from this node. */
  void add_successor( uint64_t constamp; node, int constamp; weight )
  {
    /* Manually check if this edge already exists. */
    for ( autoamp; p : successors )
    {
      if ( p.first == node )
      {
        /* If so, update its weight. */
        p.second = weight;
        return;
      }
    }
    /* If not, insert a new edge. */
    successors.emplace_back( make_pair( node, weight ) );
  }


  vector<pair<uint64_t, int>> getSuccessors(){
    return successors;
  }

  pair <uint64_t, int> getSuccessorWithMinDistance()
  {
    int minV = 999999; // minimal dist
    pair<uint64_t, int> minN;         // successor with minimal dist
    for (auto i = 0u; i < successors.size();   i)
    {
      if (successors.at(i).second <= minV)
      {
        minV = successors.at(i).second;
        minN = successors.at(i);
      }
    }
    return minN;
  }

private:
  /* List of the successors of this node. Can also be interpreted as the list of out-going edges.
     The first element of the pair is the successor node index, and the second element is the edge weight.
   */
  vector<pair<uint64_t, int>> successors;
};

class Graph
{
public:
  /* The constructor fills the vector `nodes` with `n` elements. */
  Graph( uint32_t const n )
    : nodes( n )
  {}

  void add_edge( uint64_t const from, uint64_t const to, int const weight )
  {
    if ( from == to )
    {
      return;
    }
    nodes.at( from ).add_successor( to, weight );
  }

  vector<uint64_t> dijkstra_shortest_path( uint64_t const from, uint64_t const to )
  {
    if ( from == to )
    {
      return vector<uint64_t>( 1, from ); /* Returns a vector of a single element, which is `from`. */
    }
    vector<uint64_t> minDist(nodes.size(),99999999); // Dist matrix that will store distances
    minDist[from] = 0; // 
    queue<Node> Queue; //  
    Queue.push(nodes.at(from)); // source is pushed first
    bool Visited[MAX];
    while (Queue.size() != 0)
    {

      Node Curr = Queue.front(); // node we're looking from
      Queue.pop();
      pair<uint64_t, int> Next = Curr.getSuccessorWithMinDistance(); // node we'll go to
      Node NextNode = nodes.at(Next.first);
      vector<pair<uint64_t, int>> neighbours = NextNode.getSuccessors();
      for (auto neighbour : neighbours) 
      // Curr neighbors
      // if(std::find(Visited.begin(), Visited.end(), neighbour.first) != Visited.end()){
      // }
      // else
      {
        int neighbourW = int(neighbour.second);
        int neighbourN = int(neighbour.first);
        int distThroughNeighbour = neighbourW   Next.second;
        if (distThroughNeighbour < minDist[neighbourN] amp;amp; !Visited[neighbourN])
        {
          // Curr.add_successor(nodes.at(neighbourN));
          minDist[neighbourN] = distThroughNeighbour;
          NextNode.add_successor(neighbourN, distThroughNeighbour); // add_successor will update a  vertex if the vertex already exists 
          Queue.push(NextNode); // not the right node to update amp; push ?
        }
      }
      Visited[Next.first] = 1; // too late in the execution ?
    }
    return minDist;
  }

private:
  vector<Node> nodes;
};



int main( int argc, char* argv[] )
{

  // if ( argc != 5 || ( argv[4][0] != 'd' amp;amp; argv[4][0] != 'b' ) )
  // {
  //   cerr << "[e] Please provide input file name, the source and sink nodes, and the algorithm to use." << endl;
  //   cerr << "Usage: ./hw1 <filename> <source> <sink> <d|b>" << endl;
  //   return numeric_limits<int>::min();
  // }

  ifstream fin( argv[1], ifstream::in );
  if ( !fin.is_open() )
  {
    cerr << "[e] Error opening the input file." << endl;
    return numeric_limits<int>::min();
  }

  string line, str;
  uint64_t from, to, weight;

  /* the first line contains the number of nodes (0 <= node_index <= num_nodes - 1) */
  getline( fin, line );
  Graph g( stoi( line ) );
  
  /* the remaining lines encode the edges of the graph */
  while ( getline( fin, line ) )
  {
    stringstream ss( line );

    /* the first number in each line is the "from" node */
    getline( ss, str, ' ' );
    from = stoi( str );

    /* the second number in each line is the "to" node */
    getline( ss, str, ' ' );
    to = stoi( str );

    /* the third number in each line is the weight */
    getline( ss, str, ' ' );
    weight = stoi( str );

    g.add_edge( from, to, weight );
  }
  g.dijkstra_shortest_path( 0, 5 );
  // auto const answer = argv[4][0] == 'd' ? g.dijkstra_shortest_path( atoi( argv[2] ), atoi( argv[3] ) )
  //                                       : g.bellman_ford_shortest_path( atoi( argv[2] ), atoi( argv[3] ) );

  // /* check correctness amp; compute length */
  // auto length = checker.check_path( answer, atoi( argv[2] ), atoi( argv[3] ) );
  
  // if ( length == numeric_limits<int>::min() )
  // {
  //   cout << "[e] Wrong answer: incorrect path." << endl;
  //   return length;
  // }
  // else if ( length == numeric_limits<int>::max() )
  // {
  //   cout << "[ans] Found that no path exists, or there is a negative weight loop." << endl;
  //   return length;
  // }

  // cout << "[ans] Found shortest path of length " << length << ": ";
  // for ( autoamp; n : answer )
  // {
  //   cout << n << " ";
  // }
  // cout << endl;

  // return length;
  return 0;
}
  

Входной файл в формате txt :

 10
0 1 2
0 2 3
0 3 10
1 2 3
1 3 1
2 3 3
2 4 4
0 4 3
4 6 3
3 7 3
2 6 1
3 5 4
5 7 2
7 9 1
6 8 3
8 9 0