迪杰斯特拉算法求最短路径
发布时间:2020-12-16 07:45:39 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 #include "iostream" #include "memory.h" using namespace std; const int num = 9; //节点个数 #define Infinity 65535 void dijk(int *distance,in
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 #include "iostream" #include "memory.h" using namespace std; const int num = 9; //节点个数 #define Infinity 65535 void dijk(int *distance,int *p,int graphic[num][num],int source) { //distance记录从source到其他节点的最短距离 bool isvisted[num]; //记录一个节点是否被访问过 memset(p,sizeof(p)); //记录在最短路径中,当前节点的父节点 memset(isvisted,false,sizeof(isvisted)); //初始化 for (int i = 0; i < num; i++){ distance[i] = graphic[source][i]; } isvisted[source] = true; distance[source] = 0; for (int i = 0; i < num; i++){ int min = Infinity; int index; //找出到source距离最短的未被访问过的节点 for (int j = 0; j < num; j++){ if (!isvisted[j] && distance[j] < min){ index = j; min = distance[j]; } } isvisted[index] = true; //修正其他节点到source的最短距离 for (int j = 0; j < num; j++){ if (!isvisted[j] && (min + graphic[index][j]) < distance[j]){ distance[j] = min + graphic[index][j]; p[j] = index; } } } } int main(){ int graphic[num][num]; for (int i = 0; i < num; i++) for (int j = 0; j < num; j++){ if (i == j) graphic[i][j] = 0; else graphic[i][j] = Infinity; } graphic[0][1] = 1; graphic[0][2] = 5; graphic[1][0] = 1; graphic[1][2] = 3; graphic[1][3] = 7; graphic[1][4] = 5; graphic[2][0] = 5; graphic[2][1] = 3; graphic[2][4] = 1; graphic[2][5] = 7; graphic[3][1] = 7; graphic[3][4] = 2; graphic[3][6] = 3; graphic[4][1] = 5; graphic[4][2] = 1; graphic[4][3] = 2; graphic[4][5] = 3; graphic[4][6] = 6; graphic[4][7] = 9; graphic[5][2] = 7; graphic[5][4] = 3; graphic[5][7] = 5; graphic[6][3] = 3; graphic[6][4] = 6; graphic[6][7] = 2; graphic[6][8] = 7; graphic[7][4] = 9; graphic[7][5] = 5; graphic[7][6] = 2; graphic[7][8] = 4; graphic[8][6] = 7; graphic[8][7] = 4; int distance[num]; int p[num]; dijk(distance,p,graphic,1); for (int i = 0; i < num; i++) { cout << distance[i] << endl; } return 0; } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |