最短路径算法
#include
<iostream>
void path(){
//val[i][j]从i点到j点的距离，如果不可到达到，设置成0
int val[8][8];
//res[i][j]从i点到j点的最短距离，我们只要得到res[0][7]
int res[8][8];
//fa[i]i点的前一个最短距离点
int fa[8];
for (int i = 0; i<8; i++) {
for (int j = 0; j<8; j++){
val[i][j] = 0;
res[i][j] = 10000;
}
fa[i] = -1;
}
res[0][0] = 0;
val[0][1] = 13;
val[0][2] = 15;
val[0][3] = 16;
val[1][4] = 18;
val[1][5] = 17;
val[1][6] = 16;
val[2][4] = 18;
val[2][5] = 20;
val[2][6] = 30;
val[3][4] = 11;
val[3][5] = 9;
val[3][6] = 13;
val[4][7] = 16;
val[5][7] = 14;
val[6][7] = 17;
for (int i = 1; i<8; i++) {
for (int j = 0; j<i; j++){
if (val[j][i] != 0) {
if (res[0][j] +val[j][i]<res[0][i]) {
res[0][i] = res[0][j] +val[j][i];
fa[i] = j;
}
}
}
}
int point = 7;
std::cout << 7 << "";
while (fa[point] != -1) {
std::cout << "<---" << fa[point];
point = fa[point];
}
std::cout << std::endl;
std::cout << res[0][7] <<std::endl;
}
int main(int
argc, const
char * argv[]) {
// insert code here...
std::cout << "Hello,World!\n";
path();
system("pause");
return 0;
}
运行结果：
