最短路

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径
解决算法：

floyd

dijkstra

spfa

dijktsra优化

spfa优化
dijkstra算法介绍

算法思路:

利用贪心的思想，维护一个dis数组，值为源点到各个顶点的最短距离，以及一个vis数组，表示该点已经算出最短路的点的集合

每次找到dis值最小的顶点（这个dis值就是改点到源点的最短距离），标记它，然后用它来松弛可以松弛的点，

时间复杂度：

很显然是O(n2)的
缺点：无法处理负权
代码
int dijkstra(int s,int t){
      rep(i,1,n+1){
          d[i]=g[s][i];
          vis[i]=0;
      }
      vis[s]=1;
      rep(i,2,n+1){
          int mx=inf,k=1;
          rep(j,1,n+1)if(!vis[j]&&d[j]<mx){
              mx=d[j];
              k=j;
          }
          vis[k]=1;
          rep(j,1,n+1)if(!vis[j]&&mx+g[k][j]<d[j]){
              d[j]=mx+g[k][j];
          }
      }
      return d[t]!=inf?d[t]:-1;
  }