Отслеживание кратчайшего пути между двумя узлами с использованием алгоритма Дейкстры - PullRequest
Новая
       104

Отслеживание кратчайшего пути между двумя узлами с использованием алгоритма Дейкстры

0 голосов
/ 30 мая 2020

Я новичок в c ++, и у меня возникли проблемы с изменением алгоритма Дейкстры для отслеживания кратчайшего пути между двумя узлами, а не только кратчайшего расстояния. Он правильно вычисляет кратчайшее расстояние. Это функция, которая вычисляет кратчайшее расстояние: 

  vector<vertex<T>> shortest_path(directed_graph<T> g, int u_id, int v_id) {
  vector<vertex<T>> shortest;
  vector<vector<T>> graph = g.get_adjacency_matrix();

  if (!g.contains(u_id) && !g.contains(v_id)) {
    return shortest;
  }

  shortest.push_back(vertex<T>(u_id, g.get_vert_weight(u_id)));

  int *dist = new int[g.num_vertices()]; // Will hold the shortest distance from u_id to i
  bool *sptSet = new bool[g.num_vertices()]; // Will be true if vertex i is including in shortest path tree from u_id to i

  int parent[g.num_vertices()]; // parent to store the shortest path tree

  // initialise all distances as INFINITE and set stpset as false
  for (int i = 0; i < g.num_vertices(); i++) {
    parent[u_id] = -1;
    dist[i] = INT_MAX;
    sptSet[i] = false;
  }

  dist[u_id] = 0; // Distance of source vertex to itself is always 0

  for (int count = 0; count < (g.num_vertices() - 1); count++) { // find shortest path for all vertices
    int u = min_distance(dist, sptSet, g.num_vertices()); // pick the min distance vertex from the set of vertices not yet processed
    sptSet[u] = true; // mark the picked vertex as processed

    for (int v = 0; v < g.num_vertices(); v++) { // update dist value of the adjacent vertices of the picked vertex
      // update dist[v] only if its not in sptset, there is an edge from u to v, and total weight of path from u_id to v
      // through u is smaller than current distance value of dist[v]
      if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
        parent[v] = u;
        dist[v] = dist[u] + graph[u][v];
      }
    }
  }

  for (int i = 0; i < g.num_vertices(); i++) {
    if (dist[i] != INT_MAX) {
      cout << u_id << " -> " << i << " : " << dist[i] << endl;
    } else {
      cout << u_id << " -> " << i << " : n/a" << endl;
    }
  }

  return shortest;

}

, а вот график, который я использовал для тестирования: 

    g1.add_edge(0, 1, 4);
    g1.add_edge(7, 0, 8);
    g1.add_edge(1, 7, 11);
    g1.add_edge(7, 8, 7);
    g1.add_edge(1, 2, 8);
    g1.add_edge(8, 2, 2);
    g1.add_edge(7, 6, 1);
    g1.add_edge(8, 6, 6);
    g1.add_edge(6, 5, 2);
    g1.add_edge(5, 2, 4);
    g1.add_edge(2, 3, 7);
    g1.add_edge(3, 5, 14);
    g1.add_edge(4, 3, 9);
    g1.add_edge(5, 4, 10);

Может ли кто-нибудь помочь мне с кратчайшим путем бит?

1 Ответ

0 голосов
/ 30 мая 2020

Вы можете использовать массив parent для восстановления пути, начиная от целевого узла до исходного узла, например: 

vector<int> path;
int idx = v_id;
while (idx != u_id) {
    path.emplace_back(idx);
    idx = parent[idx];
}
path.emplace_back(idx);
reverse(path.begin, path.end());
cout << "PATH: ";
for (int x : path) {
    cout << x << " ";
}
...