}
}
#endregion
二: 最短路径
1. 概念
求最短路径问题其实也是非常有实用价值的,映射到交通系统图中,就是求两个城市间的最短路径问题,还是看这张
图,我们可以很容易的看出比如
V1到图中各顶点的最短路径。
① V1 -> V2 直达, 权为2。
② V1 -> V3 直达 权为3。
③ V1->V5->V4 中转 权为3+2=5。
④ V1 -> V5 直达 权为3。
、
2. Dijkstra算法
我们的学习需要站在巨人的肩膀上,那么对于现实中非常复杂的问题,我们肯定不能用肉眼看出来,而是根据一定的算法
推导出来的。
Dijkstra思想遵循 “走一步,看一步”的原则。
第一步: 我们需要一个集合U,然后将V1放入U集合中,既然走了一步,我们就要看一步,就是比较一下V1的邻接点
(V2,V3,V5),
发现(V1,V2)的权值最小,此时我们将V2放入U集合中,表示我们已经找到了V1到V2的最短路径。
第二步:然后将V2做中间点,继续向前寻找权值最小的邻接点,发现只有V4可以连通,此时修改V4的权值为(V1,V2)+
(V2,V4)=6。
此时我们就要看一步,发现V1到(V3,V4,V5)中权值最小的是(V1,V5),此时将V5放入U集合中,表示我们
已经找到了
V1到V5的最短路径。
第三步:然后将V5做中间点,继续向前寻找权值最小的邻接点,发现能连通的有V3,V4,当我们正想修该V3的权值时发
现(V1,V3)的权值
小于(V1->V5->V3),此时我们就不修改,将V3放入U集合中,最后我们找到了V1到V3的最短路径。
第四步:因为V5还没有走完,所以继续用V5做中间点,此时只能连通(V5,V4),当要修改权值的时候,发现原来的V4权值为
(V1,V2)+(V2,V4),而
现在的权值为5,小于先前的6,此时更改原先的权值变为5,将V4放入集合中,最后我们找到了V1到V4的最短路
径。
复制代码 代码如下:
#region dijkstra求出最短路径
/// <summary>
/// dijkstra求出最短路径
/// </summary>
/// <param name="g"></param>
public void Dijkstra(MatrixGraph g)
{
int[] weight = new int[g.vertexNum];
int[] path = new int[g.vertexNum];
int[] tempvertex = new int[g.vertexNum];
Console.WriteLine("\n请输入源点的编号:");
//让用户输入要遍历的起始点