Bellman-Ford算法图解及手算过程详解——C++代码实现-创新互联
0. 《算法导论》讲解
分享名称:Bellman-Ford算法图解及手算过程详解——C++代码实现-创新互联
链接URL:http://cdiso.cn/article/dhsoeo.html
#include#includeusing namespace std;
const int n = 5;
const int INF = 0x3f3f3f3f;
typedef struct {int u;
int v;
int w;
}edge;
typedef struct {int d;
int pi;
}record;
void printRecords(record records[]) {for (int i = 0; i< n; ++i) {if (records[i].d >= INF) { cout<< "nan\t";
} else { cout<< records[i].d<< "\t";
}
}
cout<< endl;
for (int i = 0; i< n; ++i) {cout<< records[i].pi<< "\t";
}
cout<< endl<< endl;
}
vectortransform(int graph[n][n]) {vectoredges;
for (int i = 0; i< n; ++i) {for (int j = 0; j< n; ++j) { if (graph[i][j] != INF) { edge temp = {i, j, graph[i][j]};
edges.push_back(temp);
}
}
}
return edges;
}
void init(record records[n], vectoredges) {for (int i = 0; i< n; ++i) {records[i].d = INF;
records[i].pi = -1;
}
records[0].d = 0;
}
void relax(int u, int v, record records[], int graph[n][n]) {if (records[v].d >records[u].d + graph[u][v]) {records[v].d = records[u].d + graph[u][v];
records[v].pi = u;
}
}
bool bellmanFord(int graph[n][n]) {vectoredges = transform(graph);
record records[n];
init(records, edges);
printRecords(records);
for (int i = 1; i< n; ++i) {for (int j = 0; j< edges.size(); ++j) { relax(edges[j].u, edges[j].v, records, graph);
}
printRecords(records);
}
for (int k = 0; k< edges.size(); ++k) {int u = edges[k].u;
int v = edges[k].v;
if (records[v].d >records[u].d + graph[u][v]) { return false;
}
}
return true;
}
int main() {int graph[n][n] = {{INF, 6, INF, 7, INF},
{INF, INF, 5, 8, -4},
{INF, -2, INF, INF, INF},
{INF, INF, -3, INF, 9},
{2, INF, 7, INF, INF}
};
if (bellmanFord(graph)) {cout<< "true";
} else {cout<< "false";
}
return 0;
}
3. 代码运行结果
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享名称:Bellman-Ford算法图解及手算过程详解——C++代码实现-创新互联
链接URL:http://cdiso.cn/article/dhsoeo.html