Не удается найти путь между двумя точками

Question

Я пытаюсь найти путь между двумя городами (используя граф)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX 50

struct Vertex {
   char name[100];
   bool visited;
};
struct edge
{
   int weight;
   int vertexIndex;
   struct edge *edgePtr;
};
//queue variables
int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;

 //graph variables

 //array of vertices
struct Vertex* lstVertices[MAX];

//adjacency matrix
int adjMatrix[MAX][MAX];

 //vertex count
int vertexCount = 0;

//queue functions

void insert(int data) {
   queue[++rear] = data;
   queueItemCount++;
}

int removeData() {
   queueItemCount--;
   return queue[front++]; 
   }

bool isQueueEmpty() {
   return queueItemCount == 0;
}

//graph functions

//add vertex to the vertex list
void addVertex(char *name) {
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(*vertex));
   strncpy(vertex->name, name, sizeof(name));
   vertex->visited = false;
   lstVertices[vertexCount++] = vertex;
   }

//add edge to edge array
void addEdge(int start, int end, int weight_) {
   struct edge *e = (struct edge *)malloc(sizeof(*e));
   e->weight = weight_;
   adjMatrix[start][end] = e->weight;
   adjMatrix[end][start] = e->weight;
}

//display the vertex
void displayVertex(int vertexIndex){
   printf("%s ",lstVertices[vertexIndex]->name);
}       

//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
   struct edge* e = (struct edge*)malloc(sizeof(*e));
   for(int i = 0; i<vertexCount; i++) {
      if(adjMatrix[vertexIndex][i] == e->weight && lstVertices[i]->visited == false)
         return i;
      }
      
   return -1;
   }

void Search(int src, int dst) {
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
   //mark first node as visited
   lstVertices[src]->visited = true;

   //display the vertex
   displayVertex(src);   

   //insert vertex index in queue
   insert(src);
   int unvisitedVertex;

   while(!isQueueEmpty()) {
      //get the unvisited vertex of vertex which is at front of the queue
      int tempVertex = removeData();   

      //no adjacent vertex found
      while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
         }
         
      }   
      //queue is empty, search is complete, reset the visited flag        
      for(int i = 0; i<vertexCount; i++) {
         lstVertices[i]->visited = false;
      }    
   }

int main() {
   struct edge *e = (struct edge*)malloc(sizeof(*e));
   for(int i = 0; i<MAX; i++){// set adjacency
   for(int j = 0; j<MAX; j++){ // matrix to 0
      adjMatrix[i][j] = 0;
   }
   }

   addVertex("Prague");   // 0
   addVertex("Helsinki"); // 1
   addVertex("Beijing"); // 2
   addVertex("Tokyo");   // 3
   addVertex("Jakarta"); // 4
   addVertex("London");  //5
   addVertex("New York"); //6
 
   addEdge(0, 1, 1845);
   addEdge(0, 5, 1264);
   addEdge(1, 3, 7815);
   addEdge(2, 5, 4616); 
   addEdge(2, 6, 11550);
   addEdge(2, 3, 1303);
   addEdge(3, 4, 5782);
   addEdge(3, 6, 10838);
   addEdge(4, 2, 4616);
   addEdge(6, 5, 5567);
     
   printf("\nPath Found: ");
      
   Search(0, 2);

   return 0;
}

Результат:

Path Found: Prague

Желаемый результат:

Path Found: Prague, Helsinki, Tokyo, Jakarta, Beijing
Total Distance is: 20058

Кто-нибудь может помочь, пожалуйста? я новенький здесь

Answer 1

Для начала, чтобы код заработал, нужно дать возможность графу быть ориентированным:

void addEdge(int start, int end, int weight)
{
    adjMatrix[start][end] = weight;
    //adjMatrix[end][start] = weight; // это сделает граф неориентированным
}

Далее, требуются корректировки функции getAdjUnvisitedVertex(). Прямой путь в вершину имеется, если значение матрицы > 0:

int getAdjUnvisitedVertex(int vertexIndex)
{
    for (int i = 0; i < vertexCount; i++) {
        if (adjMatrix[vertexIndex][i] > 0 && lstVertices[i]->visited == false)
            return i;
    }

    return -1;
}

Чтобы иметь возможность восстановить маршрут, добавим в структуру vertex свойства from и dist:

struct Vertex {
    char name[100];
    bool visited;
    int from = -1;
    int dist = 0;
};

Функция Search(), по-хорошему, должна возвращать значение. Например, -1 - если путь не найден, индекс вершины - если найден (или true/false, не важно). Соответственно, в самой функции нужна проверка, что цель достигнута:

int Search(int src, int dst)
{
    lstVertices[src]->visited = true;

    insert(src);
    int unvisitedVertex;

    while (!isQueueEmpty()) {
        int tempVertex = removeData();

        while ((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {
            
            lstVertices[unvisitedVertex]->visited = true;
            lstVertices[unvisitedVertex]->from = tempVertex;
            lstVertices[unvisitedVertex]->dist = adjMatrix[tempVertex][unvisitedVertex];
            
            // цель достигнута?
            if (unvisitedVertex == dst)  return dst; 
            
            insert(unvisitedVertex);
        }
    }

    return 0;
}

Функция для вывода маршрута:

void printRoute(int vertex)
{
    int total = 0;

    while (lstVertices[vertex]->from > -1)
    {
        displayVertex(vertex);
        total += lstVertices[vertex]->dist;
        vertex = lstVertices[vertex]->from;
    }
    displayVertex(vertex);

    printf("\nTotal distance: %d", total);
}

Вызов в main():

if (Search(0, 2) > -1) {
    printRoute(2);
}

Вывод маршрута в обратном порядке, но это уже совсем другая история...

P.S. Исхожу из того, что задача поиска оптимального маршрута не стоит, иначе нужен принципиально другой алгоритм.

БЛОГ НА HUSL

Не удается найти путь между двумя точками

Ответы (1 шт):