图算法-用Dijkstra和Prim求最小路径

图算法-用Dijkstra和Prim求最小路径

解决问题：

在一个树中有多个节点和多条有向或无向的边，若我们给各个边附上权值，那么利用这两个算法可以计算从一个节点到所有节点的最小距离。实际中可以解决比如快递在区域配送最短的路径等问题。

Dijkstra

思路

例如以第1个节点为树根并循环整个树的节点，找到与1连接的所有点然后比较到这个点的距离是否小于原点(节点1)到这个点的距离(此时还没有)，若此时的距离比另一条路到这个点的距离小，则存入数据，以此类推。

具体如下：

我们用dist数组来存入原点到所有点的最小距离，最开始的时候设置所有的点到原点的距离为无穷大。

memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;//原点到原点的距离为0

用state数组来记录这个点是否已经找到了到原点的最小距离，如果是则记下1，否则是0。

首先用for遍历每个点，寻找到每一个点的到原点的距离。

再在用一个for来确定这个点是到原点的最短距离。

for(int i = 0; i < n; i++){
    int t = -1;
    for(int j = 1; j <= n; j++){//遍历dist数组，找到没有确定最短路径的节点中距离源点最近的点t
        if(!state[j] && (t == -1 || dist[j] < dist[t]))	t = j;
    }
    state[t] = 1;//state[i]置为1。
    for(int j = h[t]; j != -1; j = ne[j]){//遍历t所有可以到达的节点i
        int i = e[j];
        dist[i] = min(dist[i], dist[t] + w[j]);//更新dist[j]
    }
}

整个函数：

void Dijkstra(){
    memset(dist, 0x3f, sizeof(dist));//dist数组的各个元素为无穷大
    dist[1] = 0;//源点到源点的距离为置为 0
    for(int i = 0; i < n; i++){
        int t = -1;
        for(int j = 1; j <= n; j++){//遍历dist数组，找到没有确定最短路径的节点中距离源点最近的点t
            if(!state[j] && (t == -1 || dist[j] < dist[t]))	t = j;
        }
        state[t] = 1;//state[i]置为1。
        for(int j = h[t]; j != -1; j = ne[j]){//遍历t所有可以到达的节点i
            int i = e[j];
            dist[i] = min(dist[i], dist[t] + w[j]);//更新dist[j]
        }
    }
}

Prim

思路

prim 算法干的事情是：给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。prim算法相比于dijkstra是贪心的，它要寻找的是每一个点之间的最短距离。

具体如下

与Dijkstra一样用dist存入距离，并最开始用无穷大赋值。

用state数组来记录这个点是否已经找到了到原点的最小距离，如果是则记下1，否则是0。

用pre数组来保存节点是和谁连通的。

伪代码：

int dist[n],state[n],pre[n];
dist[1] = 0;
for(i : 1 ~ n)
{
    t <- 没有连通起来，但是距离连通部分最近的点;
    state[t] = 1;
    更新 dist 和 pre;
}

我们在prim里面相当于是将树的每个点一个一个加入到一个集合中，这个集合就是生成的树。每次选择树都要看看是否在树中并且到树的距离最短，如果是则加入到集合中。

void prim(){
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
    int res= 0;
    dt[1] = 0;//从 1 号节点开始生成 
    for(int i = 0; i < n; i++){//每次循环选出一个点加入到生成树
        int t = -1;
        for(int j = 1; j <= n; j++){//每个节点一次判断
            if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }
        if(dt[t] == 0x3f3f3f3f) {
            cout << "impossible";
            return;
        }
        st[t] = 1;// 选择该点
        res += dt[t];
        for(int i = 1; i <= n; i++){//更新生成树外的点到生成树的距离
            if(dt[i] > g[t][i] && !st[i]){//从 t 到节点 i 的距离小于原来距离，则更新。
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }
    cout << res;
}