【文件属性】:
文件名称:单源点最短路径算法
文件大小:2KB
文件格式:CPP
更新时间:2021-06-25 15:25:35
c++ 最短路径 C语言
struct Node
{
int distance;
int prev;
};
void PrintPath(Node* node, int source, int index)
{
if (node[index].index == source)
{
printf("M", source);
return;
}
PrintPath(node, source, node[index].prev);
printf("M", index);
}
int BellmanFord(int** matrix, int node_num, int source, int dest)
{
Node* node = new Node[node_num];
for (int i = 0; i < node_num; i++)
{
node[i].distance=100;
node[i].prev = -1;
}
node[source].distance = 0;
for (int t = 0; t < node_num; t++)
{
for (int i = 0; i < node_num; i++)
{
for (int k = 0; k < node_num; k++)
{
if (matrix[i][k] > -5 && matrix[i][k] + node[i].distance < node[k].distance)
{
node[k].distance = matrix[i][k] + node[i].distance;
node[k].prev = i;
}
}
}
}