Dijkstra朴素算法

本文主要是介绍Dijkstra朴素算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Dijkstra朴素算法

提示：此部分证明需要贪心的思想，想了解更深需查询资料

思路：

进行n次迭代确定n个点到起点的最短距离，之后输出终点到起点的最短距离。

1.首先我们需要先定义几个数组来存储图和相关的量：

int g[N][N]; //g[i][j]表示从i到j的边的权重,因为是稠密图所以用邻接矩阵
int dist[N]; //dist[i]表示i点到起点的距离
bool st[N];  //st[i]表示i点到起点的距离是否已经确定

2.然后需要对相关量进行初始化

memset(dist, 0x3f, sizeof dist); //将所有点到起点的距离初始化为无穷大
dist[1]=0; //第一个点(即起点)到起点的距离是0

3.接下来就是n次迭代：

①先定义点t，代表我们需要查找的点

int t=-1；//t就是我们需要找到的点，-1表示还没有开始寻找

②先从n个点中找到剩余未确定最短路的点中，离起点最近的点（即dist[]最小的点）

for(int j=1;j<=n;j++)
{					      //需要更新t的情况：
	if(!st[j]&&(t==-1||dist[t]>dist[j]))  //①t点的最短路还未确定②t未开始查找或者当前点的dist小于之前查找的t的dist
        t=j;
}

③此时的t点就是我们需要找的点：剩余未确定最短路的点中，离起点最近的点。将其状态设置为已经确定

st[t]=ture;

④用t点去更新其余的点到起点的最短距离

for(int j=1;j<=n;j++)
{
    if(!st[j])//此步其实是没有必要的
	dist[j]=min(dist[j],dist[t]+g[t][j]);
}

​ 因为按照我们的Dijkstra算法的操作顺序，先确定最短距离的点的距离已经比后确定的要小，所以不会影响。

4.进行n次迭代后最后就可以确定每个点的最短距离，然后再根据题意输出相应的要求的最短距离

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510;

int g[N][N]; //g[i][j]表示从i到j的边的权重,因为是稠密图所以用邻接矩阵
int dist[N]; //dist[i]表示i点到起点的距离
bool st[N];   //st[i]表示i点到起点的距离是否已经确定

int n, m;

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist); //将所有点到起点的距离初始化为无穷大

    dist[1] = 0; //第一个点(即起点)到起点的距离是0

    for (int i = 1; i <= n; i++)
    {
        int t = -1;//t就是我们需要找到的点，-1表示还没有开始寻找

        for (int j = 1; j <= n; j++)//先从n个点中找到剩余未确定最短路的点中，离起点最近的点
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;

        for (int j = 1; j <= n; j++)//用t点去更新其余的点到起点的最短距离
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;  //如果第n个点路径为无穷大即不存在最低路径
    else
        return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);     //如果发生重边的情况则保留最短的一条边
    }

    cout << Dijkstra();
    return 0;
}

这篇关于Dijkstra朴素算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！