弗洛伊德算法可以獲得圖中所有點(diǎn)，到其它任意一點(diǎn)的最短路徑。

弗洛伊德核心部分參考：https://www.cnblogs.com/wangyuliang/p/9216365.html
輸出路徑部分參考：https://blog.csdn.net/weixin_39956356/article/details/80620667

點(diǎn)：

    class Vertex
    {
        public int data;
        public Vertex(int data)
        {
            this.data = data;
        }
    }

邊：

    class Edge
    {
        public int tail;
        public int head;
        public int width;
        public Edge(int tail, int head, int width)
        {
            this.tail = tail;
            this.head = head;
            this.width = width;
        }
    }

創(chuàng)建鄰接矩陣：

    class FloydShortestPath
    {
        int[,] matrix;
        int vexCount;
        public void GraphAdjacencyMatrix(Vertex[] vex, Edge[] edge)
        {
            matrix = new int[vex.Length, vex.Length];
            for (int i = 0; i < vex.Length; i++)
            {
                for (int j = 0; j < vex.Length; j++)
                {
                    if (i != j)
                    {
                        matrix[i, j] = 1000;
                    }
                }
            }
            vexCount = vex.Length;

            for (int i = 0; i < edge.Length; i++)
            {
                int tail = edge[i].tail;
                int head = edge[i].head;
                matrix[tail, head] = edge[i].width;
                matrix[head, tail] = edge[i].width;
            }
            Console.WriteLine("鄰接矩陣：");
            Console.Write("\t ");
            for (int i = 0; i < vex.Length; i++)
            {
                Console.Write(vex[i].data + "\t ");
            }
            Console.WriteLine("\n\n");
            for (int i = 0; i < vex.Length; i++)
            {
                Console.Write(vex[i].data + "\t");
                for (int j = 0; j < vex.Length; j++)
                {
                    Console.Write("[" + matrix[i, j] + "]\t");
                }
                Console.WriteLine("\n\n");
            }
        }

Floyd算法：

        public void Floyd()
        {
            //初始化
            int[,] Fmatrix = matrix;
            int[,] Fpath = new int[vexCount, vexCount];//用來存儲終點(diǎn)前一個點(diǎn)
            for (int i = 0; i < vexCount; i++)
            {
                for (int j = 0; j < vexCount; j++)
                {
                    Fpath[i, j] = j;
                }
            }
            //核心
            for (int k = 0; k < vexCount; k++)
            {
                for (int i = 0; i < vexCount; i++)
                {
                    for (int j = 0; j < vexCount; j++)
                    {
                        if (Fmatrix[i, j] > Fmatrix[i, k] + Fmatrix[k, j])
                        {
                            Fmatrix[i, j] = Fmatrix[i, k] + Fmatrix[k, j];
                            Fpath[i, j] = Fpath[i, k];//給終點(diǎn)記錄前一個點(diǎn)
                        }
                    }
                }
            }
            //打印輸出
            for (int i = 0; i < vexCount; i++)
            {
                for (int j = 0; j < vexCount; j++)
                {
                    if (j != i)
                    {
                        Console.Write(i + " -> " + j + " weigth:" + Fmatrix[i, j] + " Path:" + i);
                        int next = i;
                        while (next != j)
                        {
                            Console.Write(" -> " + Fpath[next, j]);
                            next = Fpath[next, j];
                        }
                        Console.WriteLine();
                    }
                }
                Console.WriteLine();
            }
        }
    }
}

以下圖為例，求它的所有最短路徑：

圖

Main函數(shù)：

            FloydShortestPath floyd = new FloydShortestPath();
            Vertex vex0 = new Vertex(0);
            Vertex vex1 = new Vertex(1);
            Vertex vex2 = new Vertex(2);
            Vertex vex3 = new Vertex(3);
            Vertex vex4 = new Vertex(4);
            Vertex vex5 = new Vertex(5);
            Vertex vex6 = new Vertex(6);
            Vertex vex7 = new Vertex(7);
            Vertex vex8 = new Vertex(8);
            Vertex[] vex = { vex0, vex1, vex2, vex3, vex4, vex5, vex6, vex7, vex8 };
            Edge edge0 = new Edge(0, 1, 1);
            Edge edge1 = new Edge(0, 2, 5);
            Edge edge2 = new Edge(1, 2, 3);
            Edge edge3 = new Edge(1, 3, 7);
            Edge edge4 = new Edge(1, 4, 5);
            Edge edge5 = new Edge(2, 4, 1);
            Edge edge6 = new Edge(2, 5, 7);
            Edge edge7 = new Edge(3, 4, 2);
            Edge edge8 = new Edge(3, 6, 3);
            Edge edge9 = new Edge(4, 5, 3);
            Edge edge10 = new Edge(4, 6, 6);
            Edge edge11 = new Edge(4, 7, 9);
            Edge edge12 = new Edge(5, 7, 5);
            Edge edge13 = new Edge(6, 7, 2);
            Edge edge14 = new Edge(6, 8, 7);
            Edge edge15 = new Edge(7, 8, 4);
            Edge[] edge = { edge0, edge1, edge2, edge3, edge4, edge5, edge6, edge7, edge8, edge9, edge10, edge11, edge12, edge13, edge14, edge15 };
            floyd.GraphAdjacencyMatrix(vex, edge);
            floyd.Floyd();

運(yùn)行結(jié)果：

運(yùn)行結(jié)果