弗洛伊德算法可以获得图中所有点，到其它任意一点的最短路径。
弗洛伊德核心部分参考：https://www.cnblogs.com/wangyuliang/p/9216365.html
输出路径部分参考：https://blog.csdn.net/weixin_39956356/article/details/80620667
点：
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;
}
}
创建邻接矩阵：
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];//用来存储终点前一个点
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];//给终点记录前一个点
}
}
}
}
//打印输出
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函数：
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();
运行结果：
运行结果
