一，最短路算法的介绍

在解决最短路问题的时候我们知道的常用的算法有四种:dijkstra 最短路算法 , Bellman-ford最短路算法 ， spfa最短路算法 , floyd最短路算法 。接下来我们讲详细的介绍一下这几个算法的区别，我们直接画图来看。
在最短路问题中大致分成两种题型，首先是单源最短路， 最短路两种情况，单源最短路和多源最短路两种情况，首先我们来了解一下什么是单源最短路，什么是多源最短路？

单源最短路 ： 解决的是单个起点的最短路问题
多源最短路： 解决的是多个起点的最短路问题

我们接下来来详细的介绍一下这几个算法的实现的过程 。

二，Dijkstra最短路算法

1.算法思路和算法的适用性
算法的适应性/算法适用的条件 ： 算法只能适应在图中只有正权边的情况，无法处理负权的情况。

算法的复杂度： 算法的实现分成两种方式 ，首先是第一种朴素版的实现针对稠密图为O(n²) ,剩下的一种进行了堆优化的操作 ，时间复杂度为 O(mlogn)，用来解决稀疏图, m 为边的数量， n 为点的数量 。

算法思路 : Dijkstra算法是解决单源最短路径问题的一种贪心算法。算法采用了一个优先级队列来存储节点，从起点开始，依次扩展到与之相邻的节点，并记录到达每个节点的最短路径。

2, 算法的实现
朴素算法的实现

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

const int N = 510 ; 
int n , m ;
int g[N][N] ; 
int dist[N] ; 
bool st[N]  ;
using namespace std ;

int dijkstra () 
{
    
    
    memset(dist , 0x3f , sizeof dist ) ;
    dist[1] = 0 ; 
    //初始化操作 
    for(int j = 1 ; j <= n ; j ++ )
    {
    
        int t = - 1 ; 
        for(int i = 1 ; i <= n ; i ++ )
        {
    
            if(!st[i] &&( t == - 1 || dist[i] < dist[t] ))
                t = i ; 
        }
        st[t] = true ; 
        
        // 完成最小值的判定
        for(int i = 1 ; i <= n ; i ++ )
        {
    
        
            dist[i] = min(dist[i] , dist[t] + g[t][i]) ;
        }
    }
    
    // 最后的特判操作 
    if(dist[n] == 0x3f3f3f3f  )
        return - 1 ; 
    else return dist[n] ;
}


int main ()
{
    
    memset( g , 0x3f , sizeof g );
    cin >> n >> m ; 
    for(int i = 0 ; i < m ; i ++ )
    {
    
        int a , b , c ;
        cin >> a >> b >> c  ;
        g[a][b]  = min(g[a][b] , c ) ;
    }

    /* 主函数就是完成图的存储 */ 
    cout << dijkstra() << endl ; 
    return 0 ;
}

主要的算法的流程就是一个循环的递归的操作，首先我们分成主要的三个部分，我们把这个在下面的图中进行解释一下。
这个是简单的完成的相关的简单的朴素的算法。

优化版的 最短路算法

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std ;

const int N = 150010 ; 
int n , m ;
typedef long long LL ; 
typedef pair<int , int > PII ; 

int e[N] , h[N] , ne[N] , idx = 0  , w[N] ;
int dist[N] ;
bool st[N] ; 

void add(int a , int b , int c) 
{
    
    e[ ++ idx ] = b ; 
    w[ idx ] = c ; 
    ne[ idx ] = h[a] ;
    h[a] = idx ; 
    return ; 
}

int dijkstra() 
{
    
    memset(dist , 0x3f , sizeof dist ) ; 
    dist[1] = 0 ; 
    priority_queue < PII , vector <PII> , greater<PII> > heap ; 
    heap.push({
    0 , 1}) ; 
      while ( heap.size() )
    {
    
        PII t = heap.top() ; 
        heap.pop() ;
        int ww = t.first , ver = t.second ;
        if(st[ver]) continue ;
        st[ver] = true ; 
        for(int i = h[ver] ; i != - 1 ; i = ne[i] )
        {
    
            if(dist[e[i]] > w[i] + ww)
            {
    
                dist[e[i]] = w[i] + ww ;
                heap.push({
    dist[e[i]] , e[i]});
            }
        }
    }
    if( dist[n] == 0x3f3f3f3f )
    return - 1 ; 
    return dist[n] ;  
}

int main () 
{
    
    cin >> n >> m ; 
    memset( h , - 1 , sizeof h ) ; 
    for(int i = 1 ; i <= m ; i  ++ )
    {
    
        int a , b , c ; 
        cin >> a >> b >> c ;
        add( a , b , c ) ;
    }
    cout << dijkstra() << endl ;
    return 0 ; 
}