当前位置： 文江博客话题详情

Floyd-Warshall算法如何输出最短路径？

发布于 2024-10-09 01:33:35 字数 1839 浏览 1 评论 0原文

我正在尝试实现 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);
                }
}
原文

I'm trying to implement Floyd-Warshall algorithm (all pairs shortest path). In the code below, when I enter some numbers, it gives the last number as input. I know the code is not complete.

Now what should I do to print shortest paths for each i and j? Or what do you suggest to me to do to complete this code. Thanks.

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);
                }
}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

玩套路吗 2024-10-16 01:33:35

为了在同一页面上，让我首先向您展示 Floyd-Warshall 算法：

让我们有一个由矩阵 D 描述的图，其中 D[i][j] 是边 (i -> j) 的长度（从图的索引为 i 的顶点到索引为 j 的顶点）。

矩阵D的大小为N * N，其中N是图中的顶点总数，因为我们可以通过以下方式达到最大路径将每个图的顶点相互连接。

此外，我们还需要矩阵 R，我们将在其中存储最短路径（R[i][j] 包含最短路径中下一个顶点的索引，从顶点 i 并结束于顶点 j）。

矩阵R 的大小与D 相同。

Floyd-Warshall 算法执行以下步骤：

  1. 初始化图中任意两对或顶点之间的所有路径的矩阵，其中边的结束顶点（这很重要，因为该值将用于路径重建）

  2. 对于每对连接的顶点（读：对于每条边(u -> v)），u 和 < code>v，找到它们之间形成最短路径的顶点：如果顶点k定义了两条有效边(u -> k)和< code>(k -> v) （如果它们出现在图中），它们加起来比路径 (u -> v) 短，然后假设 u 和 v 之间的最短路径经过 k；将矩阵R中边(u -> v)的最短枢轴点设置为边(u -> k)<的对应枢轴点/code>

现在我们已经在定义的同一页面上，算法可以像这样实现：

// 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 中，它的描述如下：

有向图 G {
    0->2 [标签=“1”]；
    2->3 [标签=“5”]；
    3->1 [标签=“2”]；
    1->2 [标签=“6”]；
    1->0 [标签=“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()));
    }
}

您可以在 wikipedia 上阅读有关此算法的信息此处自动生成一些数据结构

To be on a same page, let me show you the Floyd-Warshall algorithm first:

Let us have a graph, described by matrix D, where D[i][j] is the length of edge (i -> j) (from graph's vertex with index i to the vertex with index j).

Matrix D has the size of N * N, where N is total number of vertices in graph, because we can reach the maximum of paths by connecting each graph's vertex to each other.

Also we'll need matrix R, where we will store shortest paths (R[i][j] contains the index of a next vertex in the shortest path, starting at vertex i and ending at vertex j).

Matrix R has the same size as D.

The Floyd-Warshall algorithm performs these steps:

  1. initialize the matrix of all the paths between any two pairs or vertices in a graph with the edge's end vertex (this is important, since this value will be used for path reconstruction)

  2. for each pair of connected vertices (read: for each edge (u -> v)), u and v, find the vertex, which forms shortest path between them: if the vertex k defines two valid edges (u -> k) and (k -> v) (if they are present in the graph), which are together shorter than path (u -> v), then assume the shortest path between u and v lies through k; set the shortest pivot point in matrix R for edge (u -> v) to be the corresponding pivot point for edge (u -> k)

Now that we are on a same page with definitions, algorithm can be implemented like this:

// 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];
            }
        }
    }
}

But how do we read the matrix D?

Let us have a graph:

Graph

In GraphViz it would be described as follows:

digraph G {
    0->2 [label = "1"];
    2->3 [label = "5"];
    3->1 [label = "2"];
    1->2 [label = "6"];
    1->0 [label = "7"];
}

We first create a two-dimensional array of size 4 (since there are exactly 4 vertices in our graph).

We initialize its main diagonal (the items, whose indices are equal, for ex. G[0, 0], G[1, 1], etc.) with zeros, because
the shortest path from vertex to itself has the length 0 and the other elements with a very large number (to indicate there is no edge or an infinitely long edge between them). The defined elements, corresponding to graph's edges, we fill with edges' lengths:

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;

After the algorithm run, the matrix R will be filled with vertices' indices, describing shortest paths between them. In order to reconstruct the path from vertex u to vertex v, you need follow the elements of matrix R:

List<Int32> Path = new List<Int32>();

while (start != end)
{
    Path.Add(start);

    start = R[start, end];
}

Path.Add(end);

The whole code could be wrapped in a couple of methods:

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()));
    }
}

You can read 'bout this algorithm on wikipedia and get some data structures generated automatically here

回复 原文
横笛休吹塞上声 2024-10-16 01:33:35

当您使用 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 之间的 pathS 等于“-1”。

When you are using Floyd algorithm, it saves only the shortest distance from node i to node j of your graph. So, you can also save the path to nodes. How to do it?

one of the ways to implement it - is to save the parent (the node, which is a previous node for current node in the path) node. You are to make another matrix, which will contain paths. It could look like this:

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);
            }

Now you have additional pathS array, which contains intermidiate paths between nodes i and j. For better understandning you should consider, that pathS[i,j] is a node between this two nodes (e.g. i -> [k] -> j). But your path could be longer, than 3 nodes (that's why I wrote node k in [] braces). So, now you have to check path between i and k - pathS[i,k] and path between k and j - pathS[k,j]. And do the same recursively, until pathS between some i and j equals to "-1".

回复 原文
~没有更多了~

关于作者

如果没有你

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

留蓝

文章 0 评论 0

18790681156

文章 0 评论 0

zach7772

文章 0 评论 0

Wini

文章 0 评论 0

ayeshaaroy

文章 0 评论 0

初雪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文