posted at 2021.8.31 17:28 by 风信子
旅行商最短路径的解决有二个著名的算法：迪克斯特拉（Dijkstra）和弗洛伊德（Floyed）算法。
一、迪克斯特拉（Dijkstra）在1959年发现了一个解决无向带权图中最短通路问题的算法，其中所有的权都是正数。它依赖于一系列的迭代。通过在每次迭代里添加一个顶点来构造出特殊顶点的集合。迪克斯特拉算法使用O（n^3）次运算（加法和比较）来求出连通简单无向带权图里两点之间最短通路的长度。
Dijkstra算法的基本思想是：
将图中顶点的集合分为两组S和U，并按最短路径长度的递增次序依次把集合U中的顶点加入到S中，在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
Dijkstra算法的C#代码如下：
using System;
namespace ConsoleApp1
{
class Program
{
//Dijkstra算法，cost为邻接矩阵，v为源点
static void Dijkstra(int[,] cost,int v)
{
int n = cost.GetLength(1); //顶点个数
int[] s = new int[n]; //集合S
int[] dist = new int[n]; //结果集
int[] path = new int[n]; //存放路径
for(int i = 0; i < n; i++)
{
//结果集初始化，将邻接矩阵源点所表示的行数据加进dist集合
dist[i] = cost[v, i];
if (cost[v, i] > 0) //路径初始化
{
//如果某顶点与源点存在边,则将它的前一顶点设为源点
path[i] = v;
}
else
{
//如果某顶点与源点不存在边,则将它的前一顶点值设为-1
path[i] = -i;
}
}
s[v] = 1; //将源点加进集合S
path[v] = 0;
for(int i = 0; i < n; i++)
{
//u表示剩余顶点在dist集合中的最小值所在索引
int u = 0, mindis = int.MaxValue;
for (int j = 0; j < n; j++)
{
//寻找dist集合中的最小值
if(s[j]==0 && dist[j]>0 && dist[j] < mindis)
{
u = j;
mindis = dist[j];
}
}
s[u] = 1; //将抽取出的顶点放入集合S中
for(int j = 0; j < n; j++)
{
if (s[j] == 0) //如果顶点不在集合S中
{
//加入的顶点与其余顶点存在边，并且新计算的值小于原值
if(cost[u,j]>0 && (dist[j]==0 || dist[u] + cost[u, j] < dist[j]))
{
//用更小的值代替原值
dist[j] = dist[u] + cost[u, j];
path[j] = u;
}
}
}
}
//打印源点到各顶点路径及距离
for(int i = 0; i < n; i++)
{
if (s[i] == 1)
{
Console.Write("从{0} 到{1}的最短路径为：", v, i);
Console.Write(v + "-->");
GetPath(path, i, v);
Console.Write(i);
Console.Write(" 路径长度为：" + dist[i] + "\n");
}
}
}
//使用递归获取指定顶点在路径上的前一顶点
static void GetPath(int[] Path,int i,int v)
{
int k = Path[i];
if (k == v)
{
return;
}
GetPath(Path, k, v);
Console.Write(k + "-->");
}
static void Main(string[] args)
{
int[,] cost = new int[5, 5];
//图的初始化
cost[0, 1] = 100;
cost[0, 3] = 300;
cost[0, 4] = 900;
cost[1, 2] = 500;
cost[2, 4] = 100;
cost[3, 2] = 200;
cost[3, 4] = 600;
Dijkstra(cost, 0);
}
}
}
二、弗洛伊德（Floyed）提出了另一种算法，用于计算有向图中所有顶点间的最短路径，称为弗洛伊德算法，它的时间复杂度依然为O（n^3），但形式上更为简单。弗洛伊德算法仍然使用邻接矩阵存储的图，同时定义了一个二维数组A，其每一个分量A[i,j]是顶点i到顶点j的最短路径长度。另外还使用了另一个二维数组path来保存最短路径信息。
Floyed算法的基本思想是：
（1）初始时，对图中任意两个顶点Vi和Vj，如果从Vi到Vj存在边，则从Vi到Vj存在一条长度为cost[i,j]的路径，但该路径不一定是最短路径。初始化时，A[i,j]=cost[i,j]。
（2）在图中任意两个顶点Vi和Vj之间加入顶点Vk，如果Vi经Vk到达Vj的路径存在并更短，则用A[i,k]+A[k,j]的值代替原来的A[i,j]值。
（3）重复步骤（2），直到将所有顶点作为中间点依次加入集合中，并通过选代公式不断修正A[i,j]的值，最终获得任意顶点间的最短路径长度。
Floyed算法的C#代码如下：
using System;
namespace ConsoleApp1
{
class Program1
{
//Floyed算法
static void Floyed(int[,] cost,int firstPath)
{
int n = cost.GetLength(1); //图中顶点个数
int[,] A = new int[n, n]; //存放最短路径长度
int[,] path = new int[n, n]; //存放最短路径信息
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
//辅助数组A和path的初始化
A[i, j] = cost[i, j];
path[i, j] = -1;
}
}
//弗洛伊德算法核心代码
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
//如果存在通过中间点k的路径
if(i!=j && A[i,k]!=0 && A[k, j] != 0)
{
//如果加入中间点k后的路径更短
if(A[i,j]==0 || A[i, j] > A[i, k] + A[k, j])
{
//用新路径代替原路径
A[i, j] = A[i, k] + A[k, j];
path[i, j] = k;
}
}
}
}
}
//打印最短路径及路径长度
if (firstPath==1)
{
for(int j = 0; j < n; j++)
{
if (A[firstPath, j] == 0)
{
if (firstPath != j)
{
Console.Write("从{0} 到{1}没有路径\n",firstPath,j);
}
}
else
{
Console.Write("从{0} 到{1}的路径为：", firstPath, j);
Console.Write(firstPath + "-->");
GetPath(path, firstPath, j);
Console.Write(j);
Console.Write(" 路径长度为：" + A[firstPath,j] + "\n");
}
}
Console.WriteLine();
}
}
//使用递归获取指定顶点的路径
static void GetPath(int[,] Path, int i, int j)
{
int k = Path[i,j];
if (k == -1)
{
return;
}
Console.Write(k + "-->");
GetPath(Path,k,j);
}
static void Main(string[] args)
{
int[,] cost = new int[5, 5];
//图的初始化
cost[0, 1] = 100;
cost[0, 3] = 300;
cost[0, 4] = 900;
cost[1, 2] = 500;
cost[2, 4] = 100;
cost[3, 2] = 200;
cost[3, 4] = 600;
Floyed(cost,0);
}
}
}
(最后编辑时间20210907 15:15)
0f27a943-99a5-4178-b844-2a3bf5a75f95|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: C#, 代码, 数据, 算法, 余
IT技术
