算法-作业2-floyd算法和dijkstra最短路径算法

1.问题

用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
1)Floyd

2)Dijkstra

2.解析

1）Floyd是求点i到点j的最短路径。

通过寻找中间点k,若求得i到k的路径长度和k到j的路径长度小于i直接到k的路径长度，则替换路径长度。形象比喻：北京到上海机票2000元，北京到杭州机票1100元，杭州到上海机票300元，则1100+300<2000，不考虑时间成本，经济上最优惠的方法是北京飞杭州再飞上海。

2）Dijkstra:它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
①　声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[A] = 0）。若对于顶点 A 存在能直接到达的边（A,m），则把dis[m]设为w（A, m）,同时把所有其他（A不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点A。
②　从dis数组选择最小值，则该值就是源点A到该值对应的顶点的最短路径，并且把该点加入到T中。
③　如果（新加入的顶点是否可以到达其他顶点&&通过该顶点到达其他点的路径长度是否比源点直接到达短），就替换这些顶点在dis中的值。
④　然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

3.设计

1）Floyd：

for(k=1;k<=n;k++) 
  for(i=1;i<=n;i++) 
    for(j=1;j<=n;j++) 
      if(e[i][j]>e[i][k]+e[k][j]) 
        e[i][j]=e[i][k]+e[k][j];

2）Dijkstra:

清除所有点的访问过的痕迹;
设d[0]=0，其他d[i]=INF;//INF代表极大值
For n次 { 
    在所有（未访问过&&可达）的结点中，选出路径d值最小的结点x;
    结点x设为访问过visited[x]=1;
    对于从x出发的所有边(x,y)，更新d[y] = min{d[y], d[x]+w(x,y)} 
}

4.分析

1)Floyd：三重for循环 --> O(n^3)
2)Dijkstra：首先有n次或者n-1次外层的循环遍历，这里取n次，即O(n)【从剩下的点集中选取一个距离v最小的顶点k加入到S中】比较步骤会是O(n)。【更新中间点，修改距离】的时间复杂度也为O(n)。所以，Dijkstra算法的时间复杂度为O(n*n)=O(n^2)

5.源码

github源码地址