package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int 顶点数
 * @param m int 边数
 * @param graph int二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少​
 * @return int
*/
func findShortestPath( n int ,  m int ,  graph [][]int ) int {
    // 由于我们求得是 1->n 的最短路径
    dis := make([]int, n)
    // 我们初始化 dis的 dis[0] = 0
    // write code here
    for i:=0; i<n; i++{
        // 这个地方是一个小的trick
        // 如果我们直接设置为math里面的最大值，在后续的加法当中会出现溢出的情况
        // 这里我们从题意可以得知 边的权值在0~1000 我们设置最大值为 1000×（n-1）+1
        // 这样最长路径的大小都小于这个自定义最大值， 所以如果后续dis数组里面有值等于这个自定义最大值，就知道这个点是不可达的
        dis[i] = 1000*(n-1)+1
    }
    dis[0] = 0

    // 然后我们开始v-1次松弛操作
    for i:=0; i< n-1; i++{
        for j:=0; j<m; j++{
            if dis[graph[j][0]-1]+graph[j][2] < dis[graph[j][1]-1] {
                dis[graph[j][1]-1] = dis[graph[j][0]-1]+graph[j][2]
            }
        }
    }
    // 检测是否存在 负权环 下面是伪代码
    for j:=0; j<m; j++{
            if dis[graph[j][0]-1]!=自定义最大值&&dis[graph[j][0]-1]+graph[j][2] < dis[graph[j][1]-1] {
                // 如果这个分支进入了的话 就说明存在 负权环
            }
    }

    // after before operations
    return dis[n-1]
}

时间复杂度 4ms

空间复杂度 894kb

语言 golang

bellman-ford算法简介

bellman-ford算法 是一个可以检测该图是否存在负权环的，检测的做法 就是额外的做一次松弛 如果后续的dis数组更新了，说明存在一个负权环，反之则不存在。
bellman-ford算法主要就是进行 点数-1 次松弛操作，其中每一次都会去更新dis数组，更新原则为 进来一个新的点的三元组 (u, v, w)，我们首先得到源点到u的最短距离 dis[u],和源点到v的最短距离 dis[v],然后对此次的边权进行分析，也就是判断 dis[u] + w 是否小于 dis[v], 如果小于说明这个三元组比之前的更优。

这个算法相较于dijkstra算法，他边里面可存在负权的边

举个例子 存在下面三条边 {1,2,2},{1,3,3},{3,2,-2}

1. 使用dijkstra，首先从1开始找到距离点集{1}距离最小的点 2
   紧接着找距离点集{1,2}距离最短的点，只有3了，加入进去，完成搜索。得到1-2的最短路为2 1-3的最短路为3.这个显然是不对的。
2. 使用bellman-ford算法，首先定义dis为{0，maxint，maxint}，进行第一次松弛，更新dis为{0,1,3};进行第二次松弛，dis更新为{0,1,3}，得到1-2的最短路为1, 1-3的最短路为3