027：最短路

Messj

Problem Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？



Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。


Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间


Sample Input
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0


Sample Output
3 2

Messj

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

1)算法思想原理：

     Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）

      从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

2).算法描述：

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

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

1. #include<cstdio>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int ans[101][101];
   
6. int main()
   
7. {
   
8.         int n,m;
   
9.         while(scanf("%d%d",&n,&m)!=EOF)
   
10.         {
    
11.                 if(n==0&&m==0)        break;
    
12.                 for(int i=1;i<=n;i++)
    
13.                 {
    
14.                         for(int j=1;j<=n;j++)
    
15.                                 ans[i][j]=-1;
    
16.                         ans[i][i]=0;
    
17.                 }
    
18.                 while(m--)
    
19.                 {
    
20.                         int a,b,c;
    
21.                         scanf("%d%d%d",&a,&b,&c);
    
22.                         ans[a][b]=ans[b][a]=c;
    
23.                 }
    
24.                 for(int k=1;k<=n;k++)
    
25.                         for(int i=1;i<=n;i++)
    
26.                                 for(int j=1;j<=n;j++)
    
27.                                 {
    
28.                                         if(ans[i][k]==-1||ans[k][j]==-1)
    
29.                                                 continue;
    
30.                                         if(ans[i][j]==-1||ans[i][j]>(ans[i][k]+ans[k][j]))
    
31.                                                 ans[i][j]=ans[i][k]+ans[k][j];
    
32.                                 }
    
33.                 printf("%d\n",ans[1][n]);
    
34.         }
    
35.         return 0;
    
36. }

复制代码

Messj

推荐 Dijkstra最短路径算法 文章 http://blog.csdn.net/qq_35644234/article/details/60870719

1、最短路径问题介绍

问题解释：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

解决问题的算法：

迪杰斯特拉算法（Dijkstra算法）
弗洛伊德算法（Floyd算法）
SPFA算法
这篇博客，我们就对Dijkstra算法来做一个详细的介绍

2、Dijkstra算法介绍

算法特点：

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法的思路

Dijkstra算法采用的是一种贪心的策略。
声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0(dis[ s ]=0)。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

1. #include<cstdio>
   
2. #include<vector>
   
3. #define N 101
   
4. 
   
5. using namespace std;
   
6. 
   
7. struct E
   
8. {
   
9.         int next;
   
10.         int c;
    
11. };
    
12. vector<E> edge[N];
    
13. bool mark[N];
    
14. int dis[N];
    
15. int main()
    
16. {
    
17.         int n,m;
    
18.         while(scanf("%d%d",&n,&m)!=EOF)
    
19.         {
    
20.                 if(n==0&&m==0)        break;
    
21.                 for(int i=1;i<=n;i++)        edge[i].clear();
    
22.                 while(m--)
    
23.                 {
    
24.                         int a,b,c;
    
25.                         scanf("%d%d%d",&a,&b,&c);
    
26.                         E tmp;
    
27.                         tmp.c=c;
    
28.                         tmp.next=b;
    
29.                         edge[a].push_back(tmp);
    
30.                         tmp.next=a;
    
31.                         edge[b].push_back(tmp);
    
32.                 }
    
33.                 for(int i=1;i<=n;i++)
    
34.                 {
    
35.                         dis[i]=-1;
    
36.                         mark[i]=false;
    
37.                 }
    
38.                 dis[1]=0;
    
39.                 mark[1]=true;        //点1加入集合
    
40.                 int newP=1;                //新加入集合的点为点1
    
41.                 for(int i=1;i<n;i++)
    
42.                 {
    
43.                         for(int j=0;j<edge[newP].size();j++)
    
44.                         {
    
45.                                 int t=edge[newP][j].next;
    
46.                                 int c=edge[newP][j].c;
    
47.                                 if(mark[t]==true)        continue;
    
48.                                 if(dis[t]==-1||dis[t]>(dis[newP]+c))
    
49.                                         dis[t]=dis[newP]+c;
    
50.                         }
    
51.                         int min=123123123;
    
52.                         for(int j=1;j<=n;j++)
    
53.                         {
    
54.                                 if(mark[j])        continue;
    
55.                                 if(dis[j]==-1)        continue;
    
56.                                 if(dis[j]<min)
    
57.                                 {
    
58.                                         min=dis[j];
    
59.                                         newP=j;
    
60.                                 }
    
61.                         }
    
62.                         mark[newP]=true;
    
63.                 }
    
64.                 printf("%d\n",dis[n]);
    
65.         }
    
66.         return 0;
    
67. }

复制代码