第五周练习总结

Dijkstra算法：

Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。

该算法常用于路由算法或者作为其他图算法的一个子模块。

要点：每次从 「未求出最短路径的点」中取出 距离距离起点最小路径的点，以这个点为桥梁刷新「未求出最短路径的点」的距离

思路： Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。

若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。

初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点，然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

算法图解：
1.选定A节点并初始化：

2. 找出U集合中路径最短的节点D 加入S集合，并根据条件D到B，C，E的距离加上AD的距离小于A到B，C，E的距离来更新集合U

 

3.B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离

4.

 

 5.算法结束：

 

 

用邻接矩阵实现该算法：

// Dijkstra邻接矩阵 
#include
#include
#include
using namespace std;

const int INF=0x3f3f3f3f;// 正无穷 
const int Maxsize=1e3+5;// 顶点数 
int e[Maxsize][Maxsize];// 邻接矩阵 
int book[Maxsize];// 标记 
int dis[Maxsize];// 距离表 
int n,m;// n:节点；m:边 
int v1,v2,w;

int main()
{
    scanf("%d%d",&n,&m);
    // 初始化邻接矩阵 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)e[i][j]=0;
            else e[i][j]=INF;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v1,&v2,&w);
        e[v1][v2]=w;
    }
    // init dis
    for(int i=1;i<=n;i++)
    {
        dis[i]=e[1][i];
    }
    // init book
    for(int i=1;i<=n;i++)book[i]=0;
    book[1]=1;// 程序以源点为 1来举例 
    
    for(int i=1;i<=n-1;i++)// n-1次循环，而非n次循环(因为 1节点自身已确定) 
    {
        // 找到距离1号顶点最近的顶点(min_index) 
        int min_num=INF;
        int min_index=0;
        for(int k=1;k<=n;k++)// n次循环 
        {
            if(min_num>dis[k] && book[k]==0)
            {
                min_num=dis[k];
                min_index=k;
            }
        }
        book[min_index]=1;// 标记 
        for(int j=1;j<=n;j++)
        {
            // 节点 min__index =》j 有边 
            if(e[min_index][j]dis[min_index]+e[min_index][j])
                {
                    dis[j]=dis[min_index]+e[min_index][j];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    puts("");// 换行 
    return 0;
}

 

Dijkstra算法是一种基于贪心策略的算法。

每次新扩展一个路程最短的点，更新与其相邻的点的路程。

当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。

根据这个原理，用Dijkstra算法求最短路径的图不能有负权边，因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会发生改变的性质。