迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于 1959 年提出的,因此又叫狄克斯特拉算法。 是从⼀个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。 迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 #include using namespace std; int main() { int edgs; int points; int dis[10]; int flag[10]; int infinity = 999999; cin >> points >> edgs; int edg[10][10]; for (int i = 1; i <= points; i++) { // 初始化 for (int j = 1; j <= points; j++) { if (i == j) { edg[i][j] = ___(1)___; } else { edg[i][j] = ___(2)___; } } } int point1, point2, quanzhi; for (i = 1; i <= edgs; i++) { cin >> point1 >> point2 >> quanzhi; edg[point1][point2] = ___(3)___; } for (i = 1; i <= points; i++) { dis[i] = edg[1][i]; } for (i = 1; i <= points; 1++) { flag[i] = 0; } flag[1] = 1; int min, u; for (i = 1; i <= points - 1; i++) { //源点到源点不⽤⽐较,因次总的次数少⼀次 min = infinity; for (int j = 1; j < points; j++) { if (f1ag[j] == 0 && dis[j] < min) { //核⼼思想:依次⽐较出离源点最近的点 min = ___(4)___; u = j; } } flag[u] = 1; for (int v = 1; v <= points; v++) { //找出离源点最近的点后更新dis⾥⾯的源点到各个点的 if (edg[u][v] < infinity) { if (dis[v] > dis[u] + edg[u][v]) { dis[v] = ___(5)___; } } } } for (i = 1; i <= points; i++) { cout << dis[i] < " "; } cout << endl; return 0; }
#include using namespace std; int main() { int edgs; int points; int dis[10]; int flag[10]; int infinity = 999999; cin >> points >> edgs; int edg[10][10]; for (int i = 1; i <= points; i++) { // 初始化 for (int j = 1; j <= points; j++) { if (i == j) { edg[i][j] = ___(1)___; } else { edg[i][j] = ___(2)___; } } } int point1, point2, quanzhi; for (i = 1; i <= edgs; i++) { cin >> point1 >> point2 >> quanzhi; edg[point1][point2] = ___(3)___; } for (i = 1; i <= points; i++) { dis[i] = edg[1][i]; } for (i = 1; i <= points; 1++) { flag[i] = 0; } flag[1] = 1; int min, u; for (i = 1; i <= points - 1; i++) { //源点到源点不⽤⽐较,因次总的次数少⼀次 min = infinity; for (int j = 1; j < points; j++) { if (f1ag[j] == 0 && dis[j] < min) { //核⼼思想:依次⽐较出离源点最近的点 min = ___(4)___; u = j; } } flag[u] = 1; for (int v = 1; v <= points; v++) { //找出离源点最近的点后更新dis⾥⾯的源点到各个点的 if (edg[u][v] < infinity) { if (dis[v] > dis[u] + edg[u][v]) { dis[v] = ___(5)___; } } } } for (i = 1; i <= points; i++) { cout << dis[i] < " "; } cout << endl; return 0; }
1. D
2. D
3. A
4. C
5. A
dijkstra 模板题
1. (1) 处应填( )
2. (2) 处应填( )
3. (3) 处应填( )
4. (4) 处应填( )
5. (5) 处应填( )
陈伦制作 版权所无 粤ICP备16127491号-1