我正在尝试从文本文件中读取权重,但是与手动设置权重时输出的输出不同。这是adjlist.txt文件中存在的数据:
5
8
4
2
3
9
7
2
6
7
现在,当我在没有阅读机制的情况下手动设置它们时,例如:graph-> edge [0] .weight = 5依此类推它给了我这个输出
Vertex Distance from Source
0 0
1 6
2 10
3 7
4 10
我已经尝试通过仅打印数据来获取数据,它当然可以正确读取,但不能正确解析“ cout << s [0] <
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include<bits/stdc++.h>
#include<fstream>
#include<string>
using namespace std;
// a structure to represent a weighted edge in graph
struct Edge
{
int src, dest, weight;
};
// a structure to represent a connected, directed and weighted graph
struct Graph
{
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges.
struct Edge* edge;
};
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));
return graph;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
void relax(struct Graph* graph, int V, int dist[], int E, int src)
{
for (int i = 1; i <= V - 1; i++)
{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
}
void int_source(int V,int dist[],int E,int src)
{
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
}
void negweight(struct Graph* graph, int V, int dist[], int E, int src)
{
for (int i = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
printf("Graph contains negative weight cycle");
}
}
// The main function that finds shortest distances from src to all other
// vertices using Bellman-Ford algorithm. The function also detects negative
// weight cycle
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
int_source(V,dist,E,src);
relax(graph,V,dist,E,src);
negweight(graph,V,dist,E,src);
printArr(dist, V);
return;
}
int main()
{
int V = 5; // Number of vertices in graph
int E = 10; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
string s;
cout << "Your input file contains this adjacency list\n";
ifstream infile("adjlist.txt");
while(getline(infile,s))
{
graph->edge[0].src = 1;
graph->edge[0].dest = 2;
graph->edge[0].weight = s[0]-'0';
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 1;
graph->edge[1].dest = 3;
graph->edge[1].weight = s[0]-'0';
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 4;
graph->edge[2].weight = s[0]-'0';
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 2;
graph->edge[3].dest = 1;
graph->edge[3].weight = s[0]-'0';
// add edge 1-4 (or A-E in above figure)
graph->edge[4].src = 3;
graph->edge[4].dest = 2;
graph->edge[4].weight = s[0]-'0';
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 4;
graph->edge[5].weight = s[0]-'0';
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 4;
graph->edge[6].dest = 2;
graph->edge[6].weight = s[0]-'0';
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 0;
graph->edge[7].weight = s[0]-'0';
// add edge 4-3 (or E-D in above figure)
graph->edge[8].src = 0;
graph->edge[8].dest = 1;
graph->edge[8].weight = s[0]-'0'; // add edge 4-3 (or E-D in above figure)
graph->edge[9].src = 0;
graph->edge[9].dest = 3;
graph->edge[9].weight = s[0]-'0';
}
BellmanFord(graph, 0);
return 0;
} `
预期结果应该是
Vertex Distance from Source
0 0
1 6
2 10
3 7
4 10
我得到的结果是
Vertex Distance from Source
0 0
1 7
2 14
3 7
4 14
仔细看一下主解析循环。对于从文件读取的每一行,它为所有节点的权重设置相同的值。
示例:
graph->edge[0].src = 1;
graph->edge[0].dest = 2;
graph->edge[0].weight = s[0]-'0'; // 5
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 1;
graph->edge[1].dest = 3;
graph->edge[1].weight = s[0]-'0'; // still five.
您想要的是
int index = 0;
while(getline(infile,s))
{
graph->edge[index].src = 1;
graph->edge[index].dest = 2;
graph->edge[index].weight = s[0]-'0';
index++
}
不幸的是,这似乎无法解决所有问题。我看不到进入>>正文的方法
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
使用给定的输入。
所以这个问题的答案是在@ user4581301的帮助下我更改了输入文件,因此源和目标也将添加到文件中。现在循环运行良好