前言
迪杰斯特拉算法 是求最短路径方法的其中一种，这个有什么作用呢？
有一张图:
假设求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 < vertex.Length; i++)
{
for (int j = 0; j < vertex.Length; j++)
{
Console.Write(matrix[i, j] + " ");
}
Console.WriteLine();
}
}
public void dsj(int index)
{
vv = new VisitedVertex(vertex.Length, index);
update(index);
for (int i = 1; i < vertex.Length; i++)
{
index = vv.updateArr();
update(index);
}
}
private void update(int index)
{
int len = 0;
for (int j = 0; j < vertex.Length; j++)
{
len = vv.getDis(index) + matrix[index, j];
if (!vv.isVisited(j) && len < vv.getDis(j))
{
vv.updatePre(j, index);
vv.updateDis(j, len);
}
}
}
}
class VisitedVertex
{
//记录各个顶点的访问状态
public int[] already_arr;
//每个顶点对应前一个顶点的下标
public int[] pre_visited;
//记录出发点到其他顶点的距离
public int[] dis;
public VisitedVertex(int length, int index)
{
already_arr = new int[length];
pre_visited = new int[length];
dis = new int[length];
Array.Fill(dis, int.MaxValue);
this.already_arr[index] = 1;
this.dis[index] = 0;
}
public int updateArr()
{
int min = int.MaxValue, index = 0;
for (int i = 0; i < already_arr.Length; i++)
{
if (already_arr[i] == 0 && dis[i] < min)
{
min = dis[i];
index = i;
}
}
//更新 index 顶点被访问过
already_arr[index] = 1;
return index;
}
/// <summary>
/// 是否访问过
/// </summary>
/// <param name="index">下标距离</param>
/// <returns></returns>
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();
}
}
结果:
