- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试从文本文件中读取权重,但它没有提供与我手动设置它们时相同的输出。这是 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] << "\n";"
#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++
}
不幸的是,这似乎并不能解决所有问题。我看不到进入 body 的方法
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
使用给定的输入。
关于c++ - 文本文件中的 BellmanFord 未提供与手动输入相同的输出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58617442/
我收到 3 个参数 NaN、+infinity 和 -infinity,我想通过更改 IEEE 754 数字的指数和尾数来手动生成 NaN、+inf、-inf。我怎样才能做到这一点并将其保存到 flo
我这里有这段代码。 #include #include #include int main() { int *size; int i = 0; char buf[] =
我在 Resources.Designer.cs 中添加了一个小函数,它工作得很好,问题是当我从 Resources.resx 中添加或删除某些东西时,这个函数总是被删除,有没有我可以放置的指示器还是
我首先尝试将 Entity Framework 代码用于一个简单的数据库项目,但我遇到了一个我根本无法弄清楚的问题。 我注意到 EF 将我的表的 ID 设置为每次自动增加 1,完全忽略了我为该字段手动
我是一名优秀的程序员,十分优秀!