朴素Dijkstra求最短路

题目链接

Dijkstra算法整体思路

• 进行n(n是节点个数)次遍历，找到每个节点到起点的最短距离，最后输出终点的值就是最短路距离。

  根据这个思路，我们需要

  1. 记录距离的数组
  2. 代表每一个点状态的数组

  dist[N] // 用于存储每个点到起点的最短距离
  st[N]   //    
  

• Dijkstra算法的步骤:

  1. 找出在没确定的点中距离起点距离最小的点

  int t = 0;
  for(int j = 1; j <= n; j ++)
  {
    if(!st[t] && (!t || dist[t] > dist[j]))
    {
        t = j;
    }
  }
  

  2. 更新与这个点相连的未确定点的最短距离

  for(int j = 1; j <= n; j ++)
  {
    dist[j] = min(dist[j], dist[t] + g[t][j]);
  }
  

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int g[N][N]; // 稠密图可以采用邻接矩阵存储
bool st[N];   // 判断该点的状态
int dist[N]; // 记录距离

int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    
    
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
    
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
       
        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
            
        
         st[t] = 1; // 标记该点将被确定
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    
    
    return dist[n];
}




int main()
{
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    
    int a, b, c; // 接下来m次循环传入的三个数。
    while(m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    
    int t = dijkstra();
    
    cout << t << endl;;
    
    return 0;
}