如何在Floyd-Warshall算法中输出最短路径？
Ara*_*ash 2 c# algorithm floyd-warshall
我正在尝试实现Floyd-Warshall算法(所有对最短路径).在下面的代码中,当我输入一些数字时,它将最后一个数字作为输入.我知道代码不完整.
现在我该怎么做才能为每个i和j打印最短路径？或者你建议我做些什么来完成这段代码.谢谢.
private void button10_Click(object sender, EventArgs e)
{
string ab = textBox11.Text;
int matrixDimention = Convert.ToInt32(ab);
int[,] intValues = new int[matrixDimention, matrixDimention];
string[] splitValues = textBox9.Text.Split(',');
for (int i = 0; i < splitValues.Length; i++)
intValues[i / (matrixDimention), i % (matrixDimention)] = Convert.ToInt32(splitValues[i]);
string displayString = "";
for (int inner = 0; inner < intValues.GetLength(0); inner++)
{
for (int outer = 0; outer < intValues.GetLength(0); outer++)
displayString += String.Format("{0}\t", intValues[inner, outer]);
displayString += Environment.NewLine;
}
int n = (int)Math.Pow(matrixDimention, 2);
string strn = n.ToString();
MessageBox.Show("matrix"+strn+ "in" + strn + "is\n\n\n" +displayString);
////before this line i wrote the codes to get the numbers that user enter in textbox and put it in an 2d array
for (int k = 1; k < n+1; k++)
for (int i = 1; i < n+1; i++)
for (int j = 1; j < n+1; j++)
if (intValues[i, j] > intValues[i, k] + intValues[k, j])
{
intValues[i, j] = intValues[i, k] + intValues[k, j];
string str_intvalues = intValues[i, j].ToString();
MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
}
else
{
string str_intvalues = intValues[i, j].ToString();
MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
}
}
要在同一页面上,让我先向您展示Floyd-Warshall算法:
让我们有一个由矩阵描述的图,D其中D[i][j]是边的长度(i -> j) (从图的顶点开始,索引i到带顶点的索引j).
矩阵D的大小为N * N,其中N是图中顶点的总数,因为我们可以通过将每个图的顶点相互连接来达到路径的最大值.
我们还需要矩阵R,我们将存储最短路径(R[i][j]包含最短路径中下一个顶点的索引,从顶点开始到顶点i结束j).
矩阵R具有相同的大小D.
Floyd-Warshall算法执行以下步骤:
使用边缘的末端顶点初始化图形中任意两对或顶点之间所有路径的矩阵(这很重要,因为此值将用于路径重建)
对于每对连接的顶点(读取:对于每个边
(u -> v)),u并v找到顶点,它们形成它们之间的最短路径:如果顶点k定义了两个有效边(u -> k)和(k -> v)(如果它们存在于图中),它们一起比路径(u -> v),然后假设最短的路径u和v谎言k; 将矩阵中最短的枢轴点设置R为边缘(u -> v)的对应枢轴点(u -> k)
既然我们在定义相同的页面上,算法可以像这样实现:
// Initialise the routes matrix R
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
R[i][t] = t;
}
}
// Floyd-Warshall algorithm:
for (int k = 0; k < N; k++) {
for (int u = 0; u < N; u++) {
for (int v = 0; v < N; v++) {
if (D[u, v] > D[u, k] + D[k, v]) {
D[u, v] = D[u, k] + D[k, v];
R[u, v] = R[u, k];
}
}
}
}
但我们如何阅读矩阵D？
我们有一个图表:
在GraphViz中,它将描述如下:
Run Code Online (Sandbox Code Playgroud)digraph G { 0->2 [label = "1"]; 2->3 [label = "5"]; 3->1 [label = "2"]; 1->2 [label = "6"]; 1->0 [label = "7"]; }
我们首先创建一个大小的二维数组4 (因为4我们的图中有精确的顶点).
我们初始化它的主对角线(的项目,其索引的平等,为前.G[0, 0],G[1, 1]等)以零,因为从顶点到其自身的最短路径长度0,并用大量的其他元素(表示有它们之间没有边缘或无限长的边缘).定义的元素,对应于图形的边缘,我们填充边的长度:
int N = 4;
int[,] D = new int[N, N];
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
if (i == t) {
D[i, t] = 0;
} else {
D[i, t] = 9999;
}
}
}
D[0, 2] = 1;
D[1, 0] = 7;
D[1, 2] = 6;
D[2, 3] = 5;
D[3, 1] = 2;
算法运行后,矩阵R将填充顶点索引,描述它们之间的最短路径.为了重建从顶点u到顶点的路径v,您需要遵循矩阵的元素R:
List<Int32> Path = new List<Int32>();
while (start != end)
{
Path.Add(start);
start = R[start, end];
}
Path.Add(end);
整个代码可以用几种方法包装:
using System;
using System.Collections.Generic;
public class FloydWarshallPathFinder {
private int N;
private int[,] D;
private int[,] R;
public FloydWarshallPathFinder(int NumberOfVertices, int[,] EdgesLengths) {
N = NumberOfVertices;
D = EdgesLengths;
R = null;
}
public int[,] FindAllPaths() {
R = new int[N, N];
for (int i = 0; i < N; i++)
{
for (int t = 0; t < N; t++)
{
R[i, t] = t;
}
}
for (int k = 0; k < N; k++)
{
for (int v = 0; v < N; v++)
{
for (int u = 0; u < N; u++)
{
if (D[u, k] + D[k, v] < D[u, v])
{
D[u, v] = D[u, k] + D[k, v];
R[u, v] = R[u, k];
}
}
}
}
return R;
}
public List<Int32> FindShortestPath(int start, int end) {
if (R == null) {
FindAllPaths();
}
List<Int32> Path = new List<Int32>();
while (start != end)
{
Path.Add(start);
start = R[start, end];
}
Path.Add(end);
return Path;
}
}
public class MainClass
{
public static void Main()
{
int N = 4;
int[,] D = new int[N, N];
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
if (i == t) {
D[i, t] = 0;
} else {
D[i, t] = 9999;
}
}
}
D[0, 2] = 1;
D[1, 0] = 7;
D[1, 2] = 6;
D[2, 3] = 5;
D[3, 1] = 2;
FloydWarshallPathFinder pathFinder = new FloydWarshallPathFinder(N, D);
int start = 0;
int end = 1;
Console.WriteLine("Path: {0}", String.Join(" -> ", pathFinder.FindShortestPath(start, end).ToArray()));
}
}
您可以在维基百科上阅读"回合此算法",并在此处自动生成一些数据结构
当您使用 Floyd 算法时，它只保存图表的节点 i 到节点 j 的最短距离。因此，您还可以保存节点的路径。怎么做？
实现它的方法之一 - 是保存父节点（节点，它是路径中当前节点的前一个节点）节点。您将制作另一个包含路径的矩阵。它可能看起来像这样：
int[,] pathS = new int[matrixDimention, matrixDimention];
for (int i = 0; i < splitValues.Length; i++){
intValues[i / (matrixDimention), i % (matrixDimention)] = Convert.ToInt32(splitValues[i]);
pathS[i / (matrixDimention), i % (matrixDimention)] = -1;
}
.....
for (int k = 1; k < n+1; k++)
for (int i = 1; i < n+1; i++)
for (int j = 1; j < n+1; j++)
if (intValues[i, j] > intValues[i, k] + intValues[k, j]){
intValues[i, j] = intValues[i, k] + intValues[k, j];
pathS[i,j] = k;
string str_intvalues = intValues[i, j].ToString();
MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
}
else{
string str_intvalues = intValues[i, j].ToString();
MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
}
现在您有额外的 pathS 数组，其中包含节点 i 和 j 之间的中间路径。为了更好地理解，您应该考虑，pathS[i,j] 是这两个节点之间的一个节点（例如 i -> [k] -> j）。但是你的路径可能比 3 个节点更长（这就是我在 [] 大括号中写节点 k 的原因）。因此，现在您必须检查 i 和 k 之间的路径 - pathS[i,k] 以及 k 和 j 之间的路径 - pathS[k,j]。并递归地执行相同操作，直到某些 i 和 j 之间的路径 S 等于“-1”。