Dijkstra's Shortest Circuit

Dijkstra's algorithm.

Dijkstrais an algorithm for solving the shortest path of a single source on a nonnegative weighted graph.
reasoning: Divide all nodes into two sets: the points for which the shortest path has been determined (S) and the set of points with undetermined shortest-circuit lengths (T), at the beginning all points belong to T
Initialize dist[s] = 0, all other points dis +∞
Then repeat.

1. Find the point u in the set T that is closest to the source point to be added to S
2. Point u performs a relaxation operation (updating distances to other points with u) (dis[j]=(dis[j]>dis[u]+w)?dis[u]+w:dis[j])
3. Until the T-set is not empty.
   realization
   1. The simplex approach O(n²)
   2. Priority queue version O(mlogm)

Plain Dijkstra

The graph stored with the adjacency matrix

Iterate through the dist array Find the point u that is closest to the source point that is not used to determine the shortest circuit Update the other points with u

int g[N][N],dist[N];
bool st[N];
void dijkstra()
{
    memset(dist,0x3f,sizeof d)//each point initialized to infinity first
    for(int i=1;i<=n;i++)//traverse n points
    {
        int u=0;
        for(int j=1;j<=n;j++)//traverse dist array find undetermined shortest point closest to source u
        {
            if(!st[j]&&(u==0||d[j]<d[u]))
            t=j;
    }
    //find u
    st[u]=true;
   for(int i=1;i<=n;i++)//Update the distance of other points from the source with the point u
    {
        dist[i]=min(dist[i],dist[u]+g[u][i]);
    }
}


}

Time Complexity:O(N)²)

Heap-optimized version of Dijkstra

priority_queue<PII,vector,greater>heap;// small root heap

int e[N],ne[N],h[N],W[N],idx;
int dist[N];
booo st[N];
void add(int a,int b,int c)
{
	w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}



void Dijkstra()
{
	memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;//rootlet
    ({0,1});//gap serial number
    while(())
    {
        auto u=();//未确定最短gap nearest point of origin
        ();
        int distance=,id=;
        if(st[id])continue;
        st[id]=true;
        for(int i=h[id];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]>distance+w[i])
            {
                d[j]=distance+w[i];
                (d[j],j);
            }
        }
            
        
    }
    
    
    
}
int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}

	return 0;
}

Time complexity:mlog^m