作者:NethJ | 来源:互联网 | 2023-10-09 19:38
前言迪杰斯特拉算法是求最短路径方法的其中一种,这个有什么作用呢?有一张图:假设求G点到其他各点的最小路径。是这样来的。比如找到了和G点相连接所有点,ABED。这时候确定GA是一定是
前言
迪杰斯特拉算法 是求最短路径方法的其中一种,这个有什么作用呢?
有一张图:
假设求G点到其他各点的最小路径。
是这样来的。
比如找到了和G点相连接所有点,ABED。这时候确定GA是一定是最短的,为什么这么说呢?G->A和G从别的点到A,一旦G走BED 一定会大于GA,后续就跟不可能大于了。
所以GA为最短,这时候就确定了A。这时候开始从A点开始,找到和A点相连但是没有确定最短的点,有B、C。G->A->B 大于G->B。然后A可以到C,这时候确定G->C 是9。
然后从G到各点已经相连中,找到没有确认的最小路径,这个就是确认了G->B最短。为什么能够确认呢?因为G到A然后到B大于G->B,那么可以确认G到B最短,这是因为GA是最短的,从最短的到不了,其他的一定大于G->B。
上面说其实有点模糊。
是这样的,如果从G为出发点确认了n个点,那么剩下的m个点怎么确认呢?
肯定就是从G从到先到G最短的点,尝试是否有其他路,如果没有,那么就确认了。
正文
代码如下:
class Program
{
private static int INF = int.MaxValue;
static void Main(string[] args)
{
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
int N = 65535;// 表示不可以连接
int[,] matrix = { { N, 5, 7, N, N, N, 2 },
{ 5, N, N, 9, N, N, 3 },
{ 7, N, N, N, 8, N, N },
{ N, 9, N, N, N, 4, N },
{ N, N, 8, N, N, 5, 4 },
{ N, N, N, 4, 5, N, 6 },
{ 2, 3, N, N, 4, 6, N }
};
//创建 Graph对象
Graph graph = new Graph(vertex, matrix);
//测试, 看看图的邻接矩阵是否ok
graph.showGraph();
//测试迪杰斯特拉算法
graph.dsj(2);//C
graph.showDijkstra();
Console.Read();
}
}
class Graph
{
private char[] vertex;//顶点数组
private int[,] matrix;//邻接矩阵
private VisitedVertex vv;//顶点状态
public Graph(char[] vertex, int[,] matrix)
{
this.vertex = vertex;
this.matrix = matrix;
}
public void showDijkstra()
{
vv.show();
}
public void showGraph()
{
for (int i = 0; i
/// 是否访问过
///
/// 下标距离
///
public Boolean isVisited(int index)
{
return already_arr[index] == 1;
}
//更新距离
public void updateDis(int index, int length)
{
dis[index] = length;
}
//更新前驱节点
public void updatePre(int index, int pre)
{
pre_visited[index] = pre;
}
//返回到某个节点的距离
public int getDis(int index)
{
return dis[index];
}
//显示最后的结果
//即将三个数组的情况输出
public void show()
{
Console.WriteLine("输出前驱");
//输出pre_visited
foreach (int i in pre_visited)
{
Console.Write(i + " ");
}
Console.WriteLine();
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
int count = 0;
foreach (int i in dis)
{
if (i != 65535)
{
Console.Write(vertex[count] + "(" + i + ") ");
}
else
{
Console.Write("N ");
}
count++;
}
Console.WriteLine();
}
}
结果: