#include <iostream> #include <bits/stdc++.h> using namespace std; #define Maxsize 60 typedef struct { int num;//点数 int from;//开始的点 int graph[Maxsize][Maxsize];//图 int path[Maxsize][Maxsize];//最短路径 } Graph; void Creatgraph(Graph &G)//建表 { cin >> G.num; cin >> G.from; for(int i = 0; i < G.num; i++) { for(int j = 0; j < G.num; j++) { cin >> G.graph[i][j]; if(G.graph[i][j] != 0) G.path[i][j] = G.graph[i][j]; else G.path[i][j] = 999999; } } } void Find(Graph &G) { for(int k = 0;k < G.num;k++) { for(int i = 0; i < G.num; i++) { for(int j = 0; j < G.num; j++) { if(G.path[i][k] + G.path[k][j] < G.path[i][j]) G.path[i][j] = G.path[i][k] + G.path[k][j]; } } } for(int l = 0;l < G.num;l++) { if(l == G.from) continue; if(G.path[G.from][l] < 999999) cout << G.path[G.from][l] << ' '; else cout << -1 << ' '; } cout << endl; } void Look(Graph G) { cout << "*--------*--------*" << endl; for(int i = 0; i < G.num; i++) { for(int j = 0; j < G.num; j++) { cout << G.path[i][j] << ' '; } cout << endl; } } int main() { Graph G; Creatgraph(G); Find(G); //Look(G); return 0; }解释说明
时间: 2024-04-02 11:35:39 浏览: 14
这是一个用于求解有向图最短路径的程序,使用了 Floyd 算法。具体实现过程如下:
1. 定义了一个结构体 Graph,其中包含有 num(点数)、from(开始的点)、graph(原始图)和 path(最短路径)四个成员变量。
2. 通过 Creatgraph 函数来创建图,其中从输入流中获取了 num、from 和 graph 的值。在创建过程中,将 graph 数组中为 0 的位置赋值为一个较大的数(这里是 999999),表示这两个点之间没有连通。
3. 通过 Find 函数来求解最短路径。采用了 Floyd 算法,首先对 path 数组进行初始化,然后依次枚举每一个点,通过比较当前点经过中转点 k 到达终点的路径长度与直接到达终点的路径长度的大小,更新 path 数组中两个点之间的最短路径长度。
4. 最后通过 Look 函数可以查看 path 数组中存储的每两个点之间的最短路径长度。
5. 在 main 函数中,首先创建了一个 Graph 类型的对象 G,然后调用 Creatgraph 函数来创建图,并且调用 Find 函数来求解最短路径。最后程序返回 0。
相关问题
# include <bits/stdc++.h>和# include <iostream>的区别
`#include <bits/stdc++.h>` 是一个非标准化的头文件,它包含了所有标准 C++ 库的头文件。因此,当使用这个头文件时,不需要单独包含其他头文件,就可以使用常用的 C++ 库函数和对象。
而 `#include <iostream>` 是标准 C++ 库的头文件之一,它包含了输入输出流的定义,如 `cout` 和 `cin`。这个头文件只包含输入输出流相关的内容,如果需要使用其他函数和对象,则需要包含其他相应的头文件。
因为 `#include <bits/stdc++.h>` 不是标准化的头文件,所以在编写一些需要跨平台的代码时,最好使用标准库头文件来确保代码的可移植性。
#include <iostream> #include<bits/stdcc++.h>
#include <iostream> 是C++中的一个头文件,它包含了对输入输出流的定义和操作。通过包含这个头文件,我们可以使用C++标准库中的输入输出流对象,如std::cout和std::cin。
#include<bits/stdc++.h> 是一个非标准的头文件,它包含了C++标准库中的所有头文件。这样做的目的是为了方便编程,可以省去逐个包含每个头文件的麻烦。
然而,需要注意的是,使用#include<bits/stdc++.h> 不是一个好的编程习惯,因为它会导致编译时间变长,并且可能引入一些不必要的头文件。更好的做法是只包含需要使用的具体头文件,而不是整个标准库。