Dijkstra最短路径算法,最短路径算法实例

正文实例汇报了PHP完结的迪科斯彻(Dijkstra)最短路线算法。分享给大家供我们参照他事他说加以考察,具体如下:

迪杰丝特拉(Dijkstra)算法首借使针对未有负值的有向图,求解个中的单一齐点到任何顶点的最短路线算法。本文重要计算迪杰斯特拉(Dijkstra)算法的法规和算法流程,最后经进度序实现在叁个带权值的有向图中,选定某二个源点,求解到达任何节点的最短路线,来深化对算法的知道。

迪杰斯特拉(Dijkstra)算法首如果本着未有负值的有向图,求解在那之中的纯净源点到其余顶点的最短路线算法。本文首要总结迪杰Stella(Dijkstra)算法的准则和算法流程,最后经进程序完结在三个带权值的有向图中,选定某三个源点,求解达到任何节点的最短路线,来强化对算法的通晓。

     
学习了最短路劲算法,就想用C#言语完结一下,算融洽的计算升高,也为初学者提供增加援救闲话不说,首先汇报一下dijkstra算法的思量

一、待解决难点

1 算法原理

迪杰斯特拉(Dijkstra)算法是一个如约路径长度递增的程序发生的最短路线算法。下图为带权值的有向图,作为程序中的实验数据。

图片 1

其间,带权值的有向图选用邻接矩阵graph来展打开仓库储,在企图中就是运用n*n的二维数组来进展仓储,v0-v5代表数组的索引编号0-5,二维数组的值表示节点之间的权值,若多个节点不能够通行无阻,举个例子,v0->v1不可能通行,那么$graph[0,1]=\infty$
(采取Computer中最大正整数来实行表示)。那什么样求解从v0每种v节点的最短路线长度呢?
图片 2
率先,引入三个声援数组cost,它的种种值$cost[i]$表示这几天所找到的从起首点v0到顶点vi的最短路线的权值(长度花费),该数组的初态为:若从v0到vi有弧,则$cost[i]$为弧上的权值,不然置$cost[i]$为$\infty$
。显然,长度为:
$$
cost[j]=Min_i(graph[0,i] | v_Dijkstra最短路径算法,最短路径算法实例。i \in V)
$$
的路子正是从v0出发的长短最短的一条最短路线。此路线为$(v_0,v_j)$
,那么后一次长度次短的不二秘籍必定是弧$(v_0,v_i)$ 上的权值$cost[i](v_i
\in V)$,或者是$cost[k](v_k \in S)$ 和弧$(v_k,v_i)$
的权值之和。在这之中V:待求解最短路线的节点j集合;S:已求解最短路线的节点集结。

事实上迪杰Stella(Dijkstra)最短路线算法是上一篇文迷宫难点求解之“A*搜索”(二)所讲到的
A*寻找算法中的三个特例,当A *找寻算法中
h(n)函数为0的时候,那么它正是迪杰Stella算法,算法原理一样,只不过在写程序的时候有些有一点分别而已。

1 算法原理

迪杰Stella(Dijkstra)算法是一个遵照路线长度递增的程序产生的最短路线算法。下图为带权值的有向图,作为程序中的实验数据。

图片 3

其间,带权值的有向图接纳邻接矩阵graph来展打开仓库储,在图谋中正是行使n*n的二维数组来进展仓库储存,v0-v5代表数组的索引编号0-5,二维数组的值表示节点之间的权值,若两个节点不能畅通,举个例子,v0->v1无法通行,那么$graph[0,1]=\infty$
(选拔Computer中最大正整数来拓展表示)。那怎么求解从v0每一种v节点的最短路线长度呢?
图片 4
第一,引入三个支援数组cost,它的各种值$cost[i]$表示前段时间所找到的从开端点v0到巅峰vi的最短路线的权值(长度费用),该数组的初态为:若从v0到vi有弧,则$cost[i]$为弧上的权值,不然置$cost[i]$为$\infty$
。显然,长度为:
$$
cost[j]=Min_i(graph[0,i] | v_i \in V)
$$
的路子正是从v0出发的长短最短的一条最短路线。此路线为$(v_0,v_j)$
,那么下一次长度次短的路子必定是弧$(v_0,v_i)$ 上的权值$cost[i](v_i
\in V)$,或者是$cost[k](v_k \in S)$ 和弧$(v_k,v_i)$
的权值之和。个中V:待求解最短路线的节点j会集;S:已求解最短路线的节点集合。

实际迪杰Stella(Dijkstra)最短路线算法是上一篇文迷宫难题求解之“A*搜索”(二)所讲到的
A*找出算法中的叁个特例,当A *找出算法中
h(n)函数为0的时候,那么它正是迪杰Stella算法,算法原理一样,只但是在写程序的时候有一点有一点点分别而已。

1、设置三个会集S,用来存放鲜明了最短路线的极端,贰个集结U,用来贮存未有分明最短路线的终端,贰个会集distance,表示源点到该点在那儿的最短距离,

单源最短路线难点,在加以有向图中求一个巅峰(单源顶点)到任何全体终端的最短路线难点。在下图中,每条边上有一个权值,希望求解A到独具其余顶点(B/C/D/E/F/G)的最短路线。

2 算法流程

依靠地点的算法原理解析,上面描述算法的落到实处流程。

  1. 初步化:起先化协理数组cost,从v0出发到图上别样节点v的初步权值为:$cost[i]=graph[0,i]
     |  v_i \in V$ ;伊始化待求节点S集合,它的伊始状态为空集。

  2. 分选节点$v_j$ ,使得$cost[j]=Min ( cost[i] | v_i \in V -S )$
    ,$v_j$
    正是最近求的一条从v0出发的最短路线的极限,修改S集合,使得$S=S\bigcup
    V_j$ 。

  3. 修改从v0出发到节点V-S上任一顶点$v_k$
    可达的最短路线,若cost[j]+graph[j,k]<cost[k]
    ,则修改cost[k]为:cost[k]=cost[j]+graph[j,k] 。

  4. 再一次操作2,3手续,直到求解集合V中的全数节点截至。

里面最短路径的存款和储蓄选择二个path整数数组,path[i]的值记录vi的前一个节点的目录,通过path一贯追溯到起源,就足以找到从vi到胚胎节点的最短路线。比方起初节点索引为0,若path[3]=4,
path[4]=0;那么节点v2的最短路线为,v0->v4->v3。

2 算法流程

依据地点的算法原理分析,上面描述算法的完毕流程。

  1. 开始化:开始化扶助数组cost,从v0出发到图上另外节点v的开头权值为:$cost[i]=graph[0,i]
     |  v_i \in V$ ;伊始化待求节点S集结,它的初步状态为空集。

  2. 挑选节点$v_j$ ,使得$cost[j]=Min ( cost[i] | v_i \in V -S )$
    ,$v_j$
    正是当下求的一条从v0出发的最短路线的极限,修改S群集,使得$S=S\bigcup
    V_j$ 。

  3. 修改从v0出发到节点V-S上任一顶点$v_k$
    可达的最短路线,若cost[j]+graph[j,k]<cost[k]
    ,则修改cost[k]为:cost[k]=cost[j]+graph[j,k] 。

  4. 重复操作2,3手续,直到求解集结V中的全数节点甘休。

当中最短路径的储存选取四个path整数数组,path[i]的值记录vi的前三个节点的目录,通过path一直追溯到起源,就足以找到从vi到胚胎节点的最短路径。比方起第1节点索引为0,若path[3]=4,
path[4]=0;那么节点v2的最短路线为,v0->v4->v3。

集合pre,表示该点取到当前路径时的上三个参照他事他说加以考察试的地方,开首参照他事他说加以考察试的地方下标都为0;集结Isfor表示是不是鲜明已经为最短路线了。

图片 5

3 算法达成

采用c#言语对第三节中的算法流程展开落到实处,关键代码如下。

3 算法完成

采用c#言语对第二节中的算法流程实行落到实处,关键代码如下。

2.先把源点V0的下标0加到会集S,然后标志Isfor[0]=true;把起源的下标标识为把V1,V2,V3,V4,V5,V6的下标123456放到U中,遍历集结U,把0到各类顶点的距离增添到distance中(未有直接相接的边,就用2048那一个运气表示);

二、难题解析(最短路线的子结构同样最优性)

3.1 最短路线代码

class DijkstraSolution
{
    /*
        * 求解各节点最短路径,获取path,和cost数组,
        * path[i]表示vi节点的前继节点索引,一直追溯到起点。
        * cost[i]表示vi节点的花费
        */
    public static void FindShortestPath(int[,] graph,int startIndex, int[] path, int[] cost,int max)
    {
        int nodeCount = graph.GetLength(0);
        bool[] v = new bool[nodeCount];
        //初始化 path,cost,V
        for (int i = 0; i <nodeCount ; i++)
        {
            if (i == startIndex)//如果是出发点
            {
                v[i] = true;//
            }
            else
            {
                cost[i] = graph[startIndex,i ];
                if (cost[i] < max) path[i] = startIndex;
                else path[i] = -1;
                v[i] = false;
            }
        }
        //
        for(int i=1;i<nodeCount;i++)//求解nodeCount-1个
        {
            int minCost = max ;
            int curNode=-1;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w])//未在V集合中
                { 
                    if(cost[w]<minCost)
                    {
                        minCost = cost[w];
                        curNode = w;
                    }
                }
            }//for  获取最小权值的节点
            if (curNode == -1) break;//剩下都是不可通行的节点,跳出循环
            v[curNode] = true;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w] && (graph[curNode, w] + cost[curNode] < cost[w]))
                {
                    cost[w] = graph[curNode, w] + cost[curNode];//更新权值
                    path[w] = curNode;//更新路径
                }
            }//for 更新其他节点的权值(距离)和路径
        }//
    }
}

3.1 最短路线代码

class DijkstraSolution
{
    /*
        * 求解各节点最短路径,获取path,和cost数组,
        * path[i]表示vi节点的前继节点索引,一直追溯到起点。
        * cost[i]表示vi节点的花费
        */
    public static void FindShortestPath(int[,] graph,int startIndex, int[] path, int[] cost,int max)
    {
        int nodeCount = graph.GetLength(0);
        bool[] v = new bool[nodeCount];
        //初始化 path,cost,V
        for (int i = 0; i <nodeCount ; i++)
        {
            if (i == startIndex)//如果是出发点
            {
                v[i] = true;//
            }
            else
            {
                cost[i] = graph[startIndex,i ];
                if (cost[i] < max) path[i] = startIndex;
                else path[i] = -1;
                v[i] = false;
            }
        }
        //
        for(int i=1;i<nodeCount;i++)//求解nodeCount-1个
        {
            int minCost = max ;
            int curNode=-1;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w])//未在V集合中
                { 
                    if(cost[w]<minCost)
                    {
                        minCost = cost[w];
                        curNode = w;
                    }
                }
            }//for  获取最小权值的节点
            if (curNode == -1) break;//剩下都是不可通行的节点,跳出循环
            v[curNode] = true;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w] && (graph[curNode, w] + cost[curNode] < cost[w]))
                {
                    cost[w] = graph[curNode, w] + cost[curNode];//更新权值
                    path[w] = curNode;//更新路径
                }
            }//for 更新其他节点的权值(距离)和路径
        }//
    }
}

3.遍历distance,找到最小的偏离,把顶点的下标增添到S中,然后设置该下标对应的Isfor的值为true,找到该下标为起源到各边的偏离,假诺这一个新源点到别的在U会集的终点的离开和上二个源点到新起源的偏离之和<distance数据的相距,就把该地点的distance值设为(这么些新源点到别的在U集结的极端的偏离和上三个起源到新源点的距离之和);然后退换该终端的相应pre的参照下标,为上二个源点的下标;然后再次3;

假诺P(A,G)是从顶点A到G的最短路线,要是D和F是那条路子上的中间点,那么P(D,F)一定期从D到F的最短路径。要是P(D,F)不是D到F的最短路线,这自然存在某三个节点M的另一条D到F的路径能够使P(A,B…M…F,G)比P(A,G)小,自相争辨。

3.2 调用代码

int max = 10000;
int[,] graph = new int[6, 6] {
    {max,max,10,max,30,100},
    {max,max,5,max,max,max},
    {max,max,max,50,max,max},
    {max,max,max,max,max,10},
    {max,max,max,20,max,60},
    {max,max,max,max,max,max},
};
int []path = new int[6];
int []cost = new int[6];
DijkstraSolution.FindShortestPath(graph, 0, path, cost,max);

3.2 调用代码

int max = 10000;
int[,] graph = new int[6, 6] {
    {max,max,10,max,30,100},
    {max,max,5,max,max,max},
    {max,max,max,50,max,max},
    {max,max,max,max,max,10},
    {max,max,max,20,max,60},
    {max,max,max,max,max,max},
};
int []path = new int[6];
int []cost = new int[6];
DijkstraSolution.FindShortestPath(graph, 0, path, cost,max);

附上代码:

有了那般的习性,大家能够掌握Dijkstra算法。

3.3 运转结果

图片 6

3.3 运维结果

图片 7

using System;
using System.Collections;
using System.Text;
namespace DijkstraMethod
{
class Program
{
//V1到V7的邻接矩阵
static int[,] Metro = new int[7,7] {
{ 0, 3, 7, 5,2048,2048,2048},
{ 3, 0, 2,2048, 6,2048,2048},
{ 7, 2, 0, 3, 3,2048,2048},
{ 5,2048, 3, 0,2048, 2, 8},
{2048, 6, 3,2048, 0,2048, 2},
{2048,2048,2048, 2,2048, 0, 2},
{2048,2048,2048, 8, 2, 2, 0}};
static int row = 7;
ArrayList S = new ArrayList(row);//S储存明确最短路线的顶峰的下标
ArrayList U = new ArrayList(row);//U中存款和储蓄尚未明确路线的顶点的下标
int[] distance = new int[7];//用以每趟查询寄存数据
int[] prev = new int[7];//用以存款和储蓄前三个近期终端的下标
bool[] Isfor = new bool[7] { false, false, false, false, false,
false, false };
/// <summary>
/// dijkstra算法的兑现部分
/// </summary>
/// <param name=”Start”></param>
void FindWay(int Start)
{
S.Add(Start);
Isfor[Start] = true;
for(int i=0;i<row;i++)
{
if(i!=Start)
U.Add(i);
}
for(int i=0;i<row;i++){
distance[i] = Metro[Start, i];
prev[i] = 0;
}
int Count = U.Count;
while(Count>0)
{
int min_index = (int)U[0];//假使U中第二个数存款和储蓄的是相当小的数的下标
foreach(int r in U)
{
if (distance[r] < distance[min_index]&&!Isfor[r])
min_index = r;
}
S.Add(min_index);//S出席那个近日的点
Isfor[min_index]=true;
U.Remove(min_index);//U中移除那么些点;
foreach(int r in U)
{
//查找下一行邻接矩阵,怎么着距离和上贰个源点的离开和与数组存款和储蓄的对峙统一十分小,就改动新的距离和早先点,再比对新的起源到各边的偏离
if (distance[r] > distance[min_index] + Metro[min_index,
r])
{
distance[r] = distance[min_index] + Metro[min_index, r];
prev[r] = min_index;
}
else
{
distance[r] = distance[r];
}
}
Count = U.Count;
}
}
/// <summary>
/// 把转变数据展现出来
/// </summary>
void display()
{
for(int i=0;i<row;i++)
{
Console.Write(“V1到V{0}的最短路线为→V1”,i);
int prePoint = prev[i];
string s = “”;
StringBuilder sb = new StringBuilder(10);
while (prePoint> 0)
{
s =( prePoint + 1)+s;
prePoint = prev[prePoint];
}
for (int j = 0; j < s.Length;j++ )
{
sb.Append(“-V”).Append(s[j]);
}
Console.Write(sb.ToString());
Console.Write(“-V{0}”, i );
Console.WriteLine(“:{0}”,distance[i]);

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图