Bellman Ford разбирает Source & Destination как персонаж, а не как целое число

Question

Я работаю над заданием структур данных, которое требует от меня чтения из файла, который содержит источник, назначение и вес (например, t, x, 5), и я использовал онлайн-ресурсы, такие как geeksforgeeks, откуда я изменилмой код, чтобы заставить его работать. Хотя то, что я сейчас делаю, - это своего рода обходной путь, который читает символ и преобразует его в целое число, которое в основном побеждает цель. Я хочу разобрать символы как есть, а не конвертировать их в целое число. Ссылка: https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/ Итак, в основном я делаю то, что я рассматриваю {s, t, x, y, z} как {0,1,2,3,4}, что в основном работает

if(a[0]=='s')
{
 graph->edge[index].src = 0;
}

и так далее ...

Файл, который читается

t,x,5
t,y,8
t,z,-4
x,t,-2
y,x,-3
y,z,9
z,x,7
z,s,2
s,t,6
s,y,7 

И вот рабочий код для него

#include<bits/stdc++.h>
#include<fstream>
#include<string>

using namespace std;

struct Edge { 
  int s, d, w; 
}; 
struct Graph { 
  int V, E;  
  struct Edge* edge; 
}; 
struct Graph* createGraph(int V, int E) 
{ 
  struct Graph* graph = new Graph; 
  graph->V = V; 
  graph->E = E; 
  graph->edge = new Edge[E]; 
  return graph; 
} 

void initialize_single_source(int distance[],int V, int s)
{
  for (int i = 0; i < V; i++) 
  {
    distance[i] = INT_MAX; 
  }
  distance[s] = 0; 
}

void relax(int distance[], int u, int v, int w)
{
     if (distance[v] > distance[u] + w && distance[u] != INT_MAX)
     {
        distance[v] = distance[u] + w; 
     }
}

void display(int distance[], int n) 
{ 
    char vertex[] = {'s','t','x','y','z'};
    cout << "Vertex   Distance from Source\n";
    for (int i = 0; i < n; ++i)
    cout << vertex[i] << "\t\t" << distance[i] << "\n"; 
} 

bool bellman_ford(struct Graph* graph, int s) 
{ 
  int V = graph->V; 
  int E = graph->E; 
  int distance[V]; 

  initialize_single_source(distance,V,s);

  for (int i = 1; i <= V - 1; i++)
  { 
    for (int j = 0; j < E; j++) 
    { 
      int u = graph->edge[j].s; 
      int v = graph->edge[j].d; 
      int w = graph->edge[j].w; 
      relax(distance,u,v,w);
    } 
  } 

  for (int i = 0; i < E; i++) { 
    int u = graph->edge[i].s; 
    int v = graph->edge[i].d; 
    int w = graph->edge[i].w; 
    if (distance[v] > distance[u] + w && distance[u] != INT_MAX) 
      return false; 
  } 

  display(distance, V); 

  return true; 
} 

int main() 
{ 
  int V = 5; 
  int E = 10; 
  struct Graph* graph = createGraph(V, E); 
  int index = 0;
  string a;
  ifstream infile("adjlist.txt");
  while(getline(infile,a))
{   
  if(a[0]=='s')
    {
    graph->edge[index].s = 0;
    }
    else if(a[0]=='t')
    {
    graph->edge[index].s = 1;
    }
    else if(a[0]=='x')
    {
    graph->edge[index].s = 2;
    }
    else if(a[0]=='y')
    {
    graph->edge[index].s = 3;
    }
    else if(a[0]=='z')
    {
    graph->edge[index].s = 4;
    }

    if(a[2]=='s')
    {
    graph->edge[index].d = 0;
    }
    else if(a[2]=='t')
    {
    graph->edge[index].d = 1;
    }
    else if(a[2]=='x')
    {
    graph->edge[index].d = 2;
    }
    else if(a[2]=='y')
    {
    graph->edge[index].d = 3;
    }
    else if(a[2]=='z')
    {
    graph->edge[index].d = 4;
    }

    if(a[4]!='-')
    {
    graph->edge[index].w = a[4]-'0';
    }
    else
    {
    graph->edge[index].w = -(a[5]-'0');
    }
    index++;
}
  bellman_ford(graph, 0); 

  return 0; 
} 

Вывод:

Vertex   Distance from Source
s        0
t        2
x        4
y        7
z        -2 

Answer 1

Преобразование меток вершин из строк или некоторого другого разреженного типа в плотно упакованные целые числа на самом деле довольно распространено при реализации алгоритмов графа и может быть весьма полезным.

Мы делаем это так, чтобы мы могли использовать массивы или векторы для хранения других вещей, соответствующих вершинам, вместо более сложных структур, таких как карты.

Хотя отображение меток должно быть построено динамически,в зависимости от того, какие метки у вас на самом деле вместо того, чтобы жестко его кодировать. Вы можете использовать std::map<char,int>, чтобы сделать это так:

int getVertexNumber(char c) {
    auto it = label_map.find(c);
    int num;
    if (it != label_map.end()) {
        // already had a mapping for this label
        num = it->second;
    } else {
        // new label, starting at 0
        num = (int)label_map.size();
        label_map[c] = num;
    }
    return num;
} 

Answer 2

Одним из возможных решений было бы переписать Edge следующим образом

struct Edge { 
  char s, d;
  int w;
}; 

и использовать std::map<char, vector<char> > для представления списков смежности. Обратите внимание, что для этого потребуется каким-то образом отслеживать весовые коэффициенты и соответствующим образом изменять оставшиеся части кода.

В примечании, как упомянуто @ user4581301, в том числе bits/stdc++ - плохая практика. Подробнее см. this .