Принимая кратчайший путь

Question

Эй, я пытаюсь набрать в C наименьшее количество энергии, необходимое для перемещения из одного города в другой. До сих пор я был в состоянии читать содержимое из файла. Я не уверен, что я должен делать сейчас. Код и текстовый файл имеют следующий вид:

#include <stdio.h>
#include <stdlib.h>

typedef struct value {
  int num;
  char start_vertex[250];
  char destination_vertex[250];
} value;

int main()
{
  const int nLines = 43; // number of lines in my text file
  FILE * fptr;
  value * valuesPtr = malloc(sizeof(value) * nLines);

  if (!valuesPtr) {
    puts("cannot allocate memory");
    return -1;
  }

  if((fptr = fopen("energy.txt", "r")) == NULL)
  {
    perror("Error opening file");
    return -1;
  }

  for(int i = 0; i < nLines; i++ )
  {
      if (fscanf(fptr, "%249s %249s %d",
                 valuesPtr[i].start_vertex,
                 valuesPtr[i].destination_vertex,
                 &valuesPtr[i].num) != 3) {
        printf("errored file line %d\n", i);
        break;
      }

      printf("\nStart vertex: %s \nDestination vertex: %s \nWeight: %d\n\n",
             valuesPtr[i].start_vertex, valuesPtr[i].destination_vertex, valuesPtr[i].num);
  }
  free(valuesPtr);
  fclose(fptr);

  return 0;
}

Этот код распечатывает только город отправления и назначения и энергию, необходимую для go, от одного к другому. Я хотел использовать алгоритм Беллмана-Форда или Дейкстры, но я не уверен, как реализовать их в своем коде. Это энергетический файл:

York    Hull    60
Leeds   Doncaster   -47
Liverpool   Nottingham  161
Manchester  Sheffield   61
Reading Oxford  -43
Oxford  Birmingham  103
Birmingham  Leicester   63
Liverpool   Blackpool   79
Carlisle    Newcastle   92
Nottingham  Birmingham  77
Leeds   York    39
Glasgow Edinburgh   74
Moffat  Carlisle    65
Doncaster   Hull    76
Northampton Birmingham  90
Leicester   Lincoln 82
Sheffield   Birmingham  122
Lincoln Doncaster   63
Sheffield   Doncaster   29
Bristol Reading 130
Hull    Nottingham  145
Blackpool   Leeds   116
Birmingham  Bristol 139
Manchester  Leeds   64
Carlisle    Blackpool   140
Leicester   Northampton -61
Newcastle   York    135
Glasgow Moffat  -28
Leicester   Sheffield   100
Carlisle    Liverpool   -30
Birmingham  Manchester  129
Oxford  Bristol 116
Leeds   Hull    89
Edinburgh   Carlisle    154
Nottingham  Sheffield   61
Liverpool   Manchester  56
Carlisle    Glasgow 50
Sheffield   Lincoln 74
York    Doncaster   55
Newcastle   Edinburgh   177
Leeds   Sheffield   53
Northampton Oxford  68
Manchester  Carlisle    20

Может кто-нибудь дать мне структурированный план того, что Мне нужно сделать, чтобы сделать мой алгоритм. Я хочу видеть наименьшую энергию и города, через которые вам нужно будет проехать go, чтобы go добраться от Лестера до Моффата, от Халла до Оксфорда и от Линкольна до Бристоля.

Answer 1

using System; 

класс GFG {

static int V = 9; 
int minDistance(int[] dist, 
                bool[] sptSet) 
{ 
    int min = int.MaxValue, min_index = -1; 

    for (int v = 0; v < V; v++) 
        if (sptSet[v] == false && dist[v] <= min) { 
            min = dist[v]; 
            min_index = v; 
        } 

    return min_index; 
} 

void printSolution(int[] dist, int n) 
{ 
    Console.Write("Vertex     Distance "
                  + "from Source\n"); 
    for (int i = 0; i < V; i++) 
        Console.Write(i + " \t\t " + dist[i] + "\n"); 
} 

void dijkstra(int[, ] graph, int src) 
{ 
    int[] dist = new int[V]; // The output array. dist[i] 

    bool[] sptSet = new bool[V]; 


    for (int i = 0; i < V; i++) { 
        dist[i] = int.MaxValue; 
        sptSet[i] = false; 
    } 


    dist[src] = 0; 

    for (int count = 0; count < V - 1; count++) { 
        int u = minDistance(dist, sptSet); 

        sptSet[u] = true; 

        for (int v = 0; v < V; v++) 


            if (!sptSet[v] && graph[u, v] != 0 &&  
                 dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v]) 
                dist[v] = dist[u] + graph[u, v]; 
    } 

            printSolution(dist, V); 
} 


public static void Main() 
{ 

    int[, ] graph = new int[, ] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 
                                  { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
                                  { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 
                                  { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
                                  { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
                                  { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, 
                                  { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, 
                                  { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
                                  { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; 
    GFG t = new GFG(); 
    t.dijkstra(graph, 0); 
} 

}