图论算法之Floyd算法【寻找有向图中任意两点间的最短路径 C#实现】

Folyd 算法被称为图论算法中最优美的算法，其核心代码只有 5 行，相比与 Dijkstra 算法，获取有向图中任意两点之间的距离的时间复杂度一样，都为O(N^3)，其思想类似于贪心算法，有强有力的数学理论：

Dis[a,b] = Dis[a,c] + Dis[c,b] < Dis[a,b] ? Dis[a,c] + Dis[c,b] : Dis[a,b]

上面这个表达式表示，一旦发现 a–>c–>b 距离比 a–>b 的距离更短后，就更新 Dis[a,b] 的距离为目前已知的最短距离。

Path[a,b] = Dis[a,c] + Dis[c,b] < Dis[a,b] ? Path[c,b] : Path[a,b]

上面这个表达式的意思是: 虽然我不知道 c 怎么到达 b,但是根据目前的信息我知道a 通过 c 再到达 b 的距离更短，那么 a 当然选择先到达 c ，到达 c 之后想办法怎么从 c 到达 b。

其中Path[c,b] 中存储的是一个节点，这个节点是 c–>b 的完整路径上的最后一个与 b 相连的节点。
那么当 a–>b 的路径方案改为 a–>c–>b 后，显而易见这个完整的路径的最后一个与 b 相连的节点就是 Path[c,b] 中存储的节点。

这样通过 Path[,] 可以存储所有完整路径的与终点连接的上一个节点，这样就将所有点的关系紧密联系在了一起，虽然我不知道怎么去一个点，但是我可以问他，类似于下面这样：

A 想知道怎么到达 F，但是他不知道怎么去他就这样做：
A 先去问 F ：我怎么到 F 最短； F 说：完整的路径我记不住，我只记得你通过 E 到我这最短；
A又去问 E ：我怎么到 E 最短；E 说：完整的路径我记不住，我只记得你通过 C 到我这最短；
A 先去问 C ：我怎么到 C 最短； C 说：完整的路径我记不住，我只记得你通过 D 到我这最短；
A又去问 D ：我怎么到 D 最短；D 说：完整的路径我记不住，我只记得你通过 B 到我这最短；
A又去问 B ：我怎么到 B 最短；B 说：你直接过来就是最短的；

当然，由于语言水平有限，如果没明白我在说什么也没关系，直接看代码：

核心代码：

public void FloydGetPath(int NodeNum, double[,] Amat){FloydInit(NodeNum,Amat);int k, i, j;for (k = 0; k < NodeNum; k++) //对每个节点尝试是否可以作为到达其它点的中间节点for (i = 0; i < NodeNum; i++)for (j = 0; j < NodeNum; j++)if (AdjacentMat[i, k] + AdjacentMat[k, j] < AdjacentMat[i, j]){AdjacentMat[i, j] = AdjacentMat[i, k] + AdjacentMat[k, j];//Adjacent 会不断更新 最后得到最短路径Path[i, j] = Path[k, j]; //更新 i-->j 的前驱节点//假设Path[k, j]是点 M ;//则 M 是 k --> j 完整通路的 j 的前一个节点//当 i --> j 改为通过 k 到达 j 后，那么这条完整通路的就是 i-->j-->k//明显完整通路的 j 的前一个节点也一定是 M}ShowPath();ShowAdjacentMat();ShowSinglePath(0, 6);ShowSinglePath(1, 5);}

完整工程代码：

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace Floyd算法{class Program{static void Main(string[] args){int NodeNumber = 7;//定义节点数目string ExcelPath = @\"test.xlsx\";double[,] pathdata = OpenExcel.GetDataFormExcel(ExcelPath);ShowData(pathdata);Floyd floyd = new Floyd();floyd.FloydGetPath(NodeNumber, pathdata);//第一个参数为节点数目 第二个参数为输入的 N 行 4 列的数据// 是一个N行4列的二维数组// 第0列是路段编号【不必须有】// 第1列是起点// 第2列是终点// 第3列是有向距离Console.Read();}#region  显示输入的数据static void ShowData(double[,] pathdata){int a = 0;Console.WriteLine(\"输入的数据为：\".PadRight(20));foreach (double item in pathdata){a++;MyConsole.Write(item.ToString(), 10, \' \');if (a == 4){Console.WriteLine();a = 0;}}Console.WriteLine();}#endregion}}

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace Floyd算法{class Floyd{int NodeNumber;//节点数目double[,] AdjacentMat;//邻接矩阵int[,] Path;//路径#region 初始前驱节点void FloydInit(int NodeNum,double[,] Amat){GetAdjacentMat(Amat,NodeNum);Path = new int[NodeNum, NodeNum];for (int i = 0; i < NodeNum; i++)for (int j = 0; j < NodeNum; j++){if (AdjacentMat[i, j] != double.PositiveInfinity)Path[i, j] = i;elsePath[i, j] = -1 ;}}#endregion#region Floyd主函数public void FloydGetPath(int NodeNum, double[,] Amat){FloydInit(NodeNum,Amat);int k, i, j;for (k = 0; k < NodeNum; k++) //对每个节点尝试是否可以作为到达其它点的中间节点for (i = 0; i < NodeNum; i++)for (j = 0; j < NodeNum; j++)if (AdjacentMat[i, k] + AdjacentMat[k, j] < AdjacentMat[i, j]){AdjacentMat[i, j] = AdjacentMat[i, k] + AdjacentMat[k, j];//Adjacent 会不断更新 最后得到最短路径Path[i, j] = Path[k, j]; //更新 i-->j 的前驱节点//假设Path[k, j]是点 M ;//则 M 是 k --> j 完整通路的 j 的前一个节点//当 i --> j 改为通过 k 到达 j 后，那么这条完整通路的就是 i-->j-->k//明显完整通路的 j 的前一个节点也一定是 M}ShowPath();ShowAdjacentMat();ShowSinglePath(0, 6);ShowSinglePath(1, 5);}#endregion#region 获取邻接矩阵/// <summary>/// 为邻接矩阵赋值/// </summary>/// <param name=\"Amat\">/// 是一个N行4列的二维数组/// 第0列是路段编号【不必须有】/// 第1列是起点/// 第2列是终点/// 第3列是有向距离/// </param>/// <param name=\"NodeNum\"></param>public void GetAdjacentMat(double[,] Amat, int NodeNum){NodeNumber = NodeNum;AdjacentMat = new double[NodeNumber, NodeNumber];for (int i = 0; i < NodeNum; i++)     //不连通的距离为无穷大for (int j = 0; j < NodeNum; j++){if (i == j)AdjacentMat[i, j] = 0;elseAdjacentMat[i, j] = double.PositiveInfinity;}for (int row = 0; row < Amat.GetLength(0); row++){AdjacentMat[(int)Amat[row, 1], (int)Amat[row, 2]] = Amat[row, 3];}ShowAdjacentMat();}#endregion#region 显示private void ShowAdjacentMat(){int num = 0;Console.WriteLine(\"AdjacentMat邻接矩阵：\\n\".PadRight(20));foreach (double item in AdjacentMat){MyConsole.Write(item.ToString(), 10, \' \');num++;if (num == NodeNumber){num = 0;Console.WriteLine();}}Console.WriteLine();}private void ShowPath(){int num = 0;Console.WriteLine(\"Path:\\n\");foreach (int item in Path){if (num == NodeNumber){Console.WriteLine();num = 0;}MyConsole.Write(item.ToString(), 10, \' \');num++;}Console.WriteLine(\"\\n\\n\");}private void ShowSinglePath(int startNode, int endNode){Console.WriteLine(\"从\" + startNode.ToString() + \"到\" + endNode.ToString() + \"最短路径长度为：\" + AdjacentMat[startNode, endNode].ToString() );Console.Write(\"从\" + startNode.ToString() + \"到\" + endNode.ToString() + \"最短路径为：\");List<string> singlepath = new List<string>();singlepath.Add(endNode.ToString());int pathNum = -1;int num = 0;while(pathNum !=startNode){pathNum = Path[startNode, endNode];singlepath.Add(pathNum.ToString());endNode = pathNum;}singlepath.Reverse();foreach (string item in singlepath){num++;if (num == singlepath.Count)Console.Write(item);elseConsole.Write(item + \"-->\");}Console.WriteLine(\"\\n\");}#endregion}}

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace Floyd算法{class MyConsole{public static void Write(string strOriginal,int TrueLength, char chrPad){string str = PadRightTrueLen(strOriginal, ref TrueLength, chrPad);Console.Write(str);}public static void WriteLine(string strOriginal, int TrueLength, char chrPad){string str = PadRightTrueLen(strOriginal, ref TrueLength, chrPad);Console.WriteLine(str);}/// <summary>/// 获取真实长度/// </summary>/// <param name=\"str\"></param>/// <returns></returns>public static int TrueLength(string str){int lenTotal = 0;int n = str.Length;string strWord = \"\";  //清空字符串int asc;for (int i = 0; i < n; i++){strWord = str.Substring(i, 1);asc = Convert.ToChar(strWord);if (asc < 0 || asc > 127)      // 在0~127间字符长度加1，否则加2{lenTotal = lenTotal + 2;}else{lenTotal = lenTotal + 1;}}return lenTotal;}/// <summary>/// 得到正确的格式/// </summary>/// <param name=\"strOriginal\"></param>/// <param name=\"maxTrueLength\"></param>/// <param name=\"chrPad\"></param>/// <returns></returns>private static string PadRightTrueLen(string strOriginal, ref int maxTrueLength, char chrPad){string strNew = strOriginal;if (strOriginal == null || maxTrueLength <= 0){strNew = \"\";return strNew;}int trueLen = TrueLength(strOriginal);if (trueLen > maxTrueLength)                    // 如果字符串大于规定长度 将规定长度等于字符串长度{for (int i = 0; i < trueLen - maxTrueLength; i++){maxTrueLength += chrPad.ToString().Length;}}else// 填充  小于规定长度 用‘ ’追加，直至等于规定长度{for (int i = 0; i < maxTrueLength - trueLen; i++){strNew += chrPad.ToString();}}return strNew;}}}

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Data;using System.Data.OleDb;namespace Floyd算法{class OpenExcel{public static double[,] ExcelData;public static double[,] GetDataFormExcel(string filepath){string path = filepath;//获取打开文件的路径string strCon = @\"Provider=Microsoft.Ace.OleDb.12.0;Data Source =\" + path + \";\" + \"Extended Properties=\'Excel 8.0;HDR=NO;IMEX=1;\'\";OleDbConnection myConn = new OleDbConnection(strCon);string strCom = \" select * from [Sheet1$] \";OleDbDataAdapter myCommand = new OleDbDataAdapter(strCom, myConn);DataSet myDataSet = new DataSet();myCommand.Fill(myDataSet);ExcelData = new double[myDataSet.Tables[0].Rows.Count, myDataSet.Tables[0].Columns.Count];for (int i = 0; i < myDataSet.Tables[0].Rows.Count; i++){for (int j = 0; j < myDataSet.Tables[0].Columns.Count; j++){ExcelData[i, j] = Convert.ToDouble(myDataSet.Tables[0].Rows[i][j]);}}return ExcelData;}}}