本文共 1685 字，大约阅读时间需要 5 分钟。

        给定一个带权有向图G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

        下面给出两个计算单源最短路径的模板。

①邻接矩阵：时间复杂度O(n^2)

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define INF 0x3f3f3f3f   //加上一个无限大也不会溢出using namespace std;int n;                   //顶点数int cost[105][105];      //邻接矩阵int d[105];              //距离bool used[105];          //判断是否收进最小集合void dijkstra(int s)//传入一个“单源”{	fill(d, d + n+1, INF);	fill(used, used + n+1, false);	d[s] = 0;	while (1)	{		int v = -1;		//从尚未使用的顶点中选择一个距离最小的顶点（贪心）		for (int u = 1; u <= n; u++)		{			if (!used[u] && (v == -1 || d[u] < d[v]))v = u;		}		if (v == -1)break;//没找着。		used[v] = true;		for (int u = 1; u <= n; u++)//对 和v相连的点u，更新d[u]，也是dj算法的核心（松弛），			d[u] = min(d[u], d[v] + cost[v][u]);//扫描所有的顶点，cost为INF代表没有边，走完循环d中的值还是INF，cost不为INF的就是有边咯，更新d即可。				}}
       
      
     
    
   

②：邻接表，STL优先队列优化：时间复杂度O(mlogn),适用于稀疏图

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define INF 0x3f3f3f3fstruct edge{ int to, cost; };vector
           
            G[105];//邻接表表示typedef pair
            
             P;//距离，点int M, N;int level[105];int d[105];void dijskra(int s,int min_value){ priority_queue
             
              , greater
              
 >que; //最小堆 fill(d, d + N + 1, INF); d[s] = 0; que.push(P(0, s)); while (que.size()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first)continue;//此时在其他点中更新了。 for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } }} edge tmp = { i,V }; G[T].push_back(tmp); //主程序加边T->i,权值为V。
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://iuyci.baihongyu.com/