Как изменить алгоритм Disjktra, чтобы иметь как минимум X вершин или K ребер в кратчайшем пути - PullRequest
Новая
       21

Как изменить алгоритм Disjktra, чтобы иметь как минимум X вершин или K ребер в кратчайшем пути

2 голосов
/ 27 апреля 2019

У меня есть этот алгоритм Дейкстры, хотя я хочу его изменить или можно сделать это с помощью другого алгоритма?

Мне нужно вывести вершины кратчайшего пути, хотя мне нужно иметь как минимум 5вершины (> = 5 вершин) до кратчайшего пути от начального узла до конечного узла.

В конце кода вы увидите алгоритм Дейкстры, поэтому мне нужно изменить его, чтобы я мог добавить переменнуюгде мне нужно иметь как минимум X (5 в моем случае) вершин. 

#include<iostream>
#include<set>
#include<list>
#include<algorithm>

using namespace std;

typedef struct nodes {
        int dest;
        double cost;
}node;
class Graph{

    int n;


   list<node> *adjList;

   private:
      void showList(int src, list<node> lt) {
         list<node> :: iterator i;
         node tempNode;

         for(i = lt.begin(); i != lt.end(); i++) {
            tempNode = *i;
            cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
         }
         cout << endl;
      }
   public:
      Graph() {
         n = 0;
      }

      Graph(int nodeCount) {
         n = nodeCount;
         adjList = new list<node>[n];
      }

      void addEdge(int source, int dest, double cost) {
         node newNode;
         newNode.dest = dest;
         newNode.cost = cost;
         adjList[source].push_back(newNode);
      }

      void displayEdges() {
         for(int i = 0; i<n; i++) {
            list<node> tempList = adjList[i];
            showList(i, tempList);
         }
      }

      friend void dijkstra(Graph g, double *dist, int *prev, int start);
};

void dijkstra(Graph g, double *dist, int *prev, int start) {
   int n = g.n;

   for(int u = 0; u<n; u++) {
      dist[u] = 9999;   //set as infinity
      prev[u] = -1;    //undefined previous
   }

   dist[start] = 0;   //distance of start is 0
   set<int> S;       //create empty set S
   list<int> Q;

   for(int u = 0; u<n; u++) {
      Q.push_back(u);    //add each node into queue
   }

   while(!Q.empty()) {
      list<int> :: iterator i;
      i = min_element(Q.begin(), Q.end());
      int u = *i; //the minimum element from queue
      Q.remove(u);
      S.insert(u); //add u in the set
      list<node> :: iterator it;

      for(it = g.adjList[u].begin(); it != g.adjList[u].end();it++) {
         if((dist[u]+(it->cost)) < dist[it->dest]) { //relax (u,v)
            dist[it->dest] = (dist[u]+(it->cost));
            prev[it->dest] = u;
         }
      }
   }
}

Спасибо за вашу помощь

...