GAMS 中的 Floyd–Warshall 算法

Question

我想在 GAMS 中实现 Floyd–Warshall 算法。我需要在具有正权重的加权图中找到最短路径。

下面是C++中的算法

 void Floyd_Warshal(int graph[MAX][MAX], int D[MAX][MAX], int P[MAX][MAX], int numberOfNodes){
      for(int i = 0 ; i < numberOfNodes ; i++)
        for(int j = 0 ; j < numberOfNodes ; j++){
          D[i][j] = graph[i][j];
          P[i][j] = -1;
        }
      for(int k = 0 ; k < numberOfNodes ; k++)
        for(int i = 0 ; i < numberOfNodes ; i++)
          for(int j = 0 ; j < numberOfNodes ; j++)
            if(D[i][j] > D[i][k] + D[k][j]){
              D[i][j] = D[i][k] + D[k][j];
              P[i][j] = k;
            }
      }
}

D是原图的邻接矩阵，p是路径。事实上 p 就是结果。

我可以将此代码更改为 GAMS 代码吗，我的意思是，我们可以根据此代码在 GAMS 中使用 Floyd–Warshall 算法吗？

Answer 1

看下面地址

https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_sroutex.html

类似于Floyd–Warshall算法。

GAMS 中的 Floyd–Warshall 算法

Floyd–Warshall algorithm in GAMS

gams-math