算法系列15天速成——第十五天 图【下】（大结局）

//将取得的最小节点标识为已访问
                weight[index] = short.MaxValue;
                tempvertex[index] = 0;

//从最新的节点出发，将此节点的weight比较赋值
                for (int j = 0; j < graph.vertexNum; j++)
                {
                    //已当前节点为出发点，重新选择最小边
                    if (graph.edges[index, j] < weight[j] && tempvertex[j] != used)
                    {
                        weight[j] = graph.edges[index, j];

//这里做的目的将较短的边覆盖点上一个节点的邻接点中的较长的边
                        tempvertex[j] = int.Parse(graph.vertex[index]);
                    }
                }
            }
        }
        #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></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请输入源点的编号：");

//让用户输入要遍历的起始点
            int vertex = int.Parse(Console.ReadLine()) - 1;

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!