时间戳

首页 > 解决方案 > 走最短路径

c - 走最短路径

问题描述

嘿，我正在尝试用 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;
}

此代码仅打印出出发城市和目的地城市以及从一个城市到另一个城市所需的能量。我一直在研究使用 Bellman-Ford 或 Dijkstra 算法，但我不确定如何在我的代码中实现它们这是能量文件：

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

有人可以给我一个结构化的计划来制定我的算法需要做什么。我想看看从莱斯特到莫法特、从赫尔到牛津、从林肯到布里斯托所需要的最少能源以及你必须经过的城市。

标签： cdata-structuresdijkstrabellman-ford

解决方案

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); 
}

}

推荐阅读