从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。
解决方法：
Floyd算法Bellman-Ford算法SPFA算法Dijkstra算法算法特点：可用于求出每两点之间的最短路。优点是代码简单，能够求任意两点的最短路；缺点是暴力带来的时间复杂度较大，不适合用在点较多的图中。
算法思路：定义一个二维数组dis[n][n]用于存放i点到j点的最短距离，在调用它之前只需要做简答的初始化：dis[i][i]=0，其他的dis值为正无穷inf。利用一个三重循环，去比较两点的直线距离和起点经过中转点到终点的大小，暴力遍历全图。
for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=b; j++) if(dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j];注意！这里有一个潜在的问题，如果inf太大，加法dis[i][k] + dis[k][j]可能会溢出。但如果inf太小，又可能会使得长度inf的边成为最短路的一部分。为谨慎起见，可以加一个
判断条件，如果某条边为inf，则不参与上述的加法。完整代码如下：
#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; const int num = 10001; int n, m; int dis[num][num]; void Floyd(){ for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=b; j++) if(dis[i][j]<inf && dis[k][j]<inf) if(dis[i][j] < dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; } int main(){ while(~scanf("%d%d", &n, &m)){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) dis[i][j] = inf; dis[i][i] = 0; } while(m--){ int a, b, c; scanf("%d%d%d", &a, &b, &c); int x = min(dis[a][b], c); dis[a][b] = dis[b][a] = x; } Floyd(); int s, t; scanf("%d%d", &s, &t); if(dis[s][t]==inf) printf("-1\n"); else printf("%d\n", dis[s][t]); } return 0; }