迪杰斯特拉算法（Dijkstra）：

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

1 #include 
      
         2 using namespace std;   3 const int maxnum = 100;  4 const int maxint = 999999;  5    6 // 各数组都从下标1开始  7 int dist[maxnum];     // 表示当前点到源点的最短路径长度  8 int prev[maxnum];     // 记录当前点的前一个结点  9 int c[maxnum][maxnum];   // 记录图的两点间路径长度 10 int n, line;             // 图的结点数和路径数 11   12 // n -- n nodes 13 // v -- the source node 14 // dist[] -- the distance from the ith node to the source node 15 // prev[] -- the previous node of the ith node 16 // c[][] -- every two nodes' distance 17 void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum]) 18 { 19      bool s[maxnum];    // 判断是否已存入该点到S集合中 20      for(int i=1; i<=n; ++i) 21      { 22           dist[i] = c[v][i]; 23           s[i] = 0;     // 初始都未用过该点 24           if(dist[i] == maxint) 25            prev[i] = 0; 26           else 27            prev[i] = v; 28      } 29      dist[v] = 0; 30      s[v] = 1; 31      // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中 32      // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 33         // 注意是从第二个节点开始，第一个为源点 34      for(int i=2; i<=n; ++i) 35      { 36           int tmp = maxint; 37           int u = v; 38           // 找出当前未使用的点j的dist[j]最小值 39           for(int j=1; j<=n; ++j) 40            if((!s[j]) && dist[j]
       
        =1; --i) 76       if(i != 1) 77        cout << que[i] << " -> "; 78       else 79        cout << que[i] << endl; 80 } 81   82 int main() 83 { 84   85  cin >> n; // 输入结点数 86  cin >> line; // 输入路径数 87  int p, q, len;  // 输入p, q两点及其路径长度 88   89  // 初始化c[][]为maxint 90  for(int i=1; i<=n; ++i) 91   for(int j=1; j<=n; ++j) 92    c[i][j] = maxint; 93   94  for(int i=1; i<=line; ++i)   95  { 96       cin >> p >> q >> len; 97       if(len < c[p][q])       // 有重边 98       { 99            c[p][q] = len;      // p指向q100            c[q][p] = len;      // q指向p，这样表示无向图101       }102  }103  for(int i=1; i<=n; ++i)104   dist[i] = maxint;105  for(int i=1; i<=n; ++i)106  {107       for(int j=1; j<=n; ++j)108        printf("%8d", c[i][j]);109       printf("\n");110  }111  112  Dijkstra(n, 1, dist, prev, c);113  //最短路径长度114  cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;115  //路径116  cout << "源点到最后一个顶点的路径为: ";117  searchPath(prev, 1, n);118 }
       
      

1 #include 
     
       2 #include 
      
        3 #define inf 99999999 4 #define MAX 100 5  6 int n;  7 int dis[MAX]; 8 int path[MAX][MAX]; 9 int visit[MAX];10 int dijkstra () //起点从1开始  输出起点到终点的最短路径 11 {12     int i,j,pos,minn;13     for (i = 1; i <= n; i ++)14     {15         dis[i] = path[1][i];16         visit[i] = 0;17     }18     dis[1] = 0;19     visit[1] = 1;20     for(i = 1;i <= n; i ++)21     {22         minn = inf;23         for (j = 1; j <= n; j ++)24             if (!visit[j] && dis[j] < minn)25             {26                 minn = dis[j];27                 pos = j;28             }    29         visit[pos] = 1;30         for (j = 1; j <= n; j ++)31         {32             if (!visit[j] && dis[j] > dis[pos]+path[pos][j])33                 dis[j] = dis[pos]+path[pos][j];34         }35     }36     return dis[n]; 37 }
      
     

 

弗洛伊德算法（Floyd算法）：

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，

同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N³)，空间复杂度为O(N²)。

 

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　

 

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

1 #include 
     
       2 #include 
      
        3 #define inf 99999999 4 #define MAX 100 5  6 int n; 7 int path[MAX][MAX]; 8 int floyd() //任意两点之间的最短路径  9 {10     int i,j,k;11     for (k = 1; k <= n; k ++)12         for (i = 1; i <= n; i ++)13             for (j = 1; j <= n; j ++)14                 if (path[i][j] > path[i][k]+path[k][j])15                     path[i][j] = path[i][k]+path[k][j];16     return path[1][n];17 }
      
     

 

Mellman-Frod算法：

适用条件&范围：

单源最短路径(从源点s到其它所有顶点v);

有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

边权可正可负(如有负权回路输出错误提示);

Bellman－Ford算法可以大致分为三个部分

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。

第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。

第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：

d（v） > d (u) + w(u,v)

则返回false，表示途中存在从源点可达的权为负的回路。

1 #include
       
           2 #include
        
            3 using namespace std;   4    5 #define MAX 0x3f3f3f3f   6 #define N 1010   7 int nodenum, edgenum, original; //点，边，起点   8    9 typedef struct Edge //边  10 {  11     int u, v;  12     int cost;  13 }Edge;  14   15 Edge edge[N];  16 int dis[N], pre[N];  17   18 bool Bellman_Ford()  19 {  20     for(int i = 1; i <= nodenum; ++i) //初始化  21         dis[i] = (i == original ? 0 : MAX);  22     for(int i = 1; i <= nodenum - 1; ++i)  23         for(int j = 1; j <= edgenum; ++j)  24             if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）  25             {  26                 dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;  27                 pre[edge[j].v] = edge[j].u;  28             }  29             bool flag = 1; //判断是否含有负权回路  30             for(int i = 1; i <= edgenum; ++i)  31                 if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)  32                 {  33                     flag = 0;  34                     break;  35                 }  36                 return flag;  37 }  38   39 void print_path(int root) //打印最短路的路径（反向）  40 {  41     while(root != pre[root]) //前驱  42     {  43         printf("%d-->", root);  44         root = pre[root];  45     }  46     if(root == pre[root])  47         printf("%d\n", root);  48 }  49   50 int main()  51 {  52     scanf("%d%d%d", &nodenum, &edgenum, &original);  53     pre[original] = original;  54     for(int i = 1; i <= edgenum; ++i)  55     {  56         scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);  57     }  58     if(Bellman_Ford())  59         for(int i = 1; i <= nodenum; ++i) //每个点最短路  60         {  61             printf("%d\n", dis[i]);  62             printf("Path:");  63             print_path(i);  64         }  65     else  66         printf("have negative circle\n");  67     return 0;  68 }
        
       

 

1 #include 
      
        2 #include 
       
         3 #define inf 99999999 4 #define MAX 100 5  6 struct land  7 { 8     int x,y,z;         9 }path[MAX]; 10 void add(int u,int v,int w) //从u到v路径为w11 {12     path[ans].x = u;13     path[ans].y = v;14     path[ans].z = w;15     ans ++;16 } 17 int n; //n个节点18 int ans; //ans条路 19 int path[MAX][MAX];20 bool Bellman_ford() //判断是否出现正环或负环21 {22     int i,j;23     for (i = 1; i <= n; i ++)24         dis[i] = inf;25     dis[1] = 0;26     27     for (i = 1; i < n; i ++)  //n-1次循环28     {29         bool flag = false;  //优化 30         for(j = 0; j < m; j ++)  //松弛m条路31             if(dis[path[j].y] > dis[path[j].x]+path[j].z)32             {33                 dis[path[j].y] = dis[path[j].x]+path[j].z;34                 flag = true;35             }36         if (!flag)  //不能松弛，表示一定不存在负权值回路 37             return false;38     }39     40     for (j = 0; j < m; j ++)41         if (dis[path[j].y] > dis[path[j].x]+path[j].z)42             return true;43     return false;44 }
       
      

 

SPFA算法：

推荐博客：

　　　　

适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。

算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止

以POJ1511为例

1 #include 
       
          2 #include 
        
           3 #define inf 9999999999  4 #include 
         
            5 #include 
          
             6 #include 
           
              7 using namespace std;  8 struct node  9 { 10     int to; 11     int w; 12     int next; 13 }; 14 queue 
            
              q; 15 int n,m; 16 node list[1000010]; 17 node list1[1000010]; 18 int vis[1000010]; 19 int dis[1000010]; 20 int h1[1000010]; 21 int h2[1000010]; 22 void spfa() 23 { 24 int i,j,u; 25 for (i = 1; i <= n; i ++) 26 { 27 dis[i] = inf; 28 vis[i] = 0; 29 } 30 q.push(1); 31 dis[1] = 0; 32 vis[1] = 1; 33 34 while (!q.empty()) 35 { 36 u = q.front(); 37 q.pop(); 38 vis[u] = 0; 39 for (j = h1[u]; j ; j = list[j].next) 40 { 41 if (dis[list[j].to] > dis[u]+list[j].w) 42 { 43 dis[list[j].to] = dis[u]+list[j].w; 44 if (!vis[list[j].to]) 45 { 46 q.push(list[j].to); 47 vis[list[j].to] = 1; 48 } 49 } 50 } 51 } 52 } 53 void spfa1() 54 { 55 int i,j,u; 56 for (i = 1; i <= n; i ++) 57 { 58 dis[i] = inf; 59 vis[i] = 0; 60 } 61 q.push(1); 62 dis[1] = 0; 63 vis[1] = 1; 64 65 while (!q.empty()) 66 { 67 u = q.front(); 68 q.pop(); 69 vis[u] = 0; 70 for (j = h2[u]; j ; j = list1[j].next) 71 { 72 if (dis[list1[j].to] > dis[u]+list1[j].w) 73 { 74 dis[list1[j].to] = dis[u]+list1[j].w; 75 if (!vis[list1[j].to]) 76 { 77 q.push(list1[j].to); 78 vis[list1[j].to] = 1; 79 } 80 } 81 } 82 } 83 } 84 int main () 85 { 86 int i,j,t,u,v,w,ans; 87 scanf("%d",&t); 88 while (t --) 89 { 90 scanf("%d%d",&n,&m); 91 memset(h1,0,sizeof(h1)); 92 memset(h2,0,sizeof(h2)); 93 for (ans = 1,i = 0; i < m; i ++) 94 { 95 scanf("%d%d%d",&u,&v,&w); 96 node temp = {v,w,0}; 97 list[ans] = temp; 98 list[ans].next = h1[u]; 99 h1[u] = ans;100 temp.to = u;101 list1[ans] = temp;102 list1[ans].next = h2[v];103 h2[v] = ans;104 ans ++;105 }106 long long sum = 0;107 spfa();108 for (i = 1; i <= n; i ++)109 sum += dis[i];110 spfa1();111 for (i = 1; i <= n; i ++)112 sum += dis[i];113 printf("%lld\n",sum);114 }115 return 0;116 }