dijkstra大神发明的算法

朴素的dijkstra算法时间复杂度为O(nn)，只能处理包含正权边的图。

使用优先级队列或堆优化过的dijkstra算法时间复杂度为O(Nlog(N))

下面是优先级队列优化的dijkstra代码源码

/*input:点数 N，边数 M，起点S，终点T，以及M组路线(起点 终点 终点)*/#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define maxN 1024#define maxM 10240int n, m, s, t;struct node{    int to, cost, next;}edge[maxM<<1];int first[maxN], edgeCnt;int addEdge(int from, int to, int cost){    edge[edgeCnt].to = to;    edge[edgeCnt].cost = cost;    edge[edgeCnt].next = first[from];    return first[from] = edgeCnt++;}void buildGraph(){    int a, b, c;    edgeCnt = 0;    memset(first, -1, sizeof(first));    for(int i=0; i
        
          b.cost;    }};priority_queue
         
           myQueue;int solve(){ struct qnode tmp; memset(dist, -1, sizeof(dist)); tmp.pos = s; tmp.cost = 0; myQueue.push(tmp); while(myQueue.size() > 0 && dist[t] == -1){ tmp = myQueue.top(); myQueue.pop(); if(dist[tmp.pos] != -1) continue; int from = tmp.pos; dist[from] = tmp.cost; for(int e = first[from]; e != -1; e = edge[e].next){ if(dist[edge[e].to] != -1) continue; tmp.pos = edge[e].to, tmp.cost = dist[from] + edge[e].cost; myQueue.push(tmp); } } return dist[t];}int main(){// freopen("1.txt", "r", stdin); scanf("%d %d %d %d", &n, &m, &s, &t); buildGraph(); cout << solve(); return 0;}
         
        
       
      
     
    

下面是朴素的dijkstra算法

#include
    
     #include
     
      #define maxa 1005#define INF 10000000int n,m;int dis[maxa];bool mark[maxa];int map[maxa][maxa];int mon[maxa];void dijkstra(int s){    int i,j,k,Min,visa,p;    memset(mark,0,sizeof(mark));    for(i=1; i<=n; i++)    {        dis[i]=map[s][i];            }    dis[s]=0;    mon[s]=0;    mark[s]=1;    for(i=1; i