Skip to content

Latest commit

 

History

History
241 lines (227 loc) · 6.35 KB

最短路径.md

File metadata and controls

241 lines (227 loc) · 6.35 KB
Raw

1.dijkstra算法

算法的思路：

  1. 已知起点，初始化从起点到其它位置的距离为无穷大，并初始化起点到起点的距离为0
  2. 从没有访问过的点中选出距离最短的点
  3. 以此点为起点，依此访问它的邻接点，并更新为最短距离
  4. 记录路径
const int inf = 0x3f3f3f3;
int dist[1000],road[1000][1000],vis[1000],path[1000];
void dijskstra(int start,int n) {
    memset(vis,0,sizeof(vis));
    fill(dist,dist+n,inf);
    dist[start] = 0;
    for(int i = 0; i < n; i++) {
        int min = inf,u = -1;
        //选出距离最短的点
        for(int k = 0; k < n; k++) {
            if(dist[k] > min && !vis[k]) {
                min = dist[k];
                u = k;
            }
        }
        if(u == -1) return;
        vis[u] = 1;//置为访问
        int shortest = dist[u];
        for(int v = 0; v < n; v++) {
            if(!vis[v] && road[u][v] != 0) {
                if(dist[v] > shortest + road[u][v]) {
                    dist[v] = shortest + road[u][v];
                    path[v] = u;//记录路径,当前点的前驱为最短路径的点
                }
            }
        }
    }
}

2. dijkstra算法优先队列优化

const int inf = 0x3f3f3f3f;
struct node {
    int no;
    int distance;
    bool operator< (const node &t) const {return distance > t.distance;}
    //这里一定是distance > t.distance
};

vector< vector<node> > road;
priority_queue<node> qu;
int path[1000],vis[1000],dist[1000];
void dijsktra(int start,int n) {
    fill(dist,dist + n,inf);
    for(int i = 0; i <= n; i++) path[i] = i;
    memset(vis,0,sizeof(vis));
    dist[start] = 0;
    qu.push({start,0});
    while(!qu.empty()) {
        node tmp = qu.top();qu.pop();
        int no = tmp.no;
        int distance = tmp.distance;
        if(vis[no]) continue;
        vis[no] = 1;
        for(int i = 0; i < road[no].size(); i++) {
            node v = road[no][i];
            int curi = v.no,curdis = distance + v.distance;
            if(dist[curi] > curdis) {
                path[curi] = no;
                dist[curi] = curdis;
                qu.push(node{curi,dist[curi]});
                //这里是push当前节点和当前节点的dist距离
            }
        }
    }
}

3.SPFA最短路径算法

#include <bits/stdc++.h>
using namespace std;
const int Maxsize = 2e4 + 5,inf = 0x3f3f3f3f;
int n,m,dist[Maxsize],path[Maxsize],e[Maxsize][Maxsize];
bool vis[Maxsize];
void SPFA(int start)
{
    memset(dist,inf,sizeof(dist));
    memset(vis,false,sizeof(vis));
    for(int i = 0; i < Maxsize; ++i) path[i] = i;
    dist[start] = 0;
    queue<int> qu;
    qu.push(start);
    while(!qu.empty())
    {
        int u = qu.front(); qu.pop();
        vis[u] = false;//将处理的结点出队
        for(int v = 1; v <= n; ++v)
        {
            if(dist[v] > dist[u] + e[u][v])
            {
                dist[v] = dist[u] + e[u][v];
                path[v] = u;
                if(!vis[v])//如果这个结点没有在队列
                {
                    vis[v] = true;//入队
                    qu.push(v);//入队
                }
            }
        }
    }
}
void dfs(int u,int v)
{
    if(u == v)
    {
        printf("%d ",u);
        return;
    }
    dfs(u,path[v]);
    printf("%d ",v);
}
int main()
{
    int u,v,l;
    memset(e,inf,sizeof(e));
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d",&u,&v,&l);
        e[u][v] = l;
    }
    SPFA(1);
    for(int i = 2; i <= n; ++i) printf("%d\n",dist[i]);
    return 0;
}
/*
5 5
1 2 -3
1 5 5
2 3 2
3 4 3
4 5 2
*/

4.dijkstra最短路径记录多条

const int inf = 0x3f3f3f3f;
struct node {
    int no;
    int distance;
    bool operator< (const node &t) const {return distance > t.distance;}
    //这里一定是distance > t.distance
};

vector< vector<node> > road;
priority_queue<node> qu;
int vis[1000],dist[1000];
//path记录多条，用二维数组
vector<int> path[1000];
void dijsktra(int start,int n) {
    fill(dist,dist + n,inf);
    memset(vis,0,sizeof(vis));
    dist[start] = 0;
    qu.push({start,0});
    while(!qu.empty()) {
        node tmp = qu.top();qu.pop();
        int no = tmp.no;
        int distance = tmp.distance;
        if(vis[no]) continue;
        vis[no] = 1;
        for(int i = 0; i < road[no].size(); i++) {
            node v = road[no][i];
            int curi = v.no,curdis = distance + v.distance;
            if(dist[curi] > curdis) {
                path[curi].clear();//把当前节点的全部路径给清楚掉
                //然后再push进去
                path[curi].push_back(no);
                dist[curi] = curdis;
                qu.push(node{curi,dist[curi]});
                //这里是push当前节点和当前节点的dist距离
            } else if(dist[curi] == curdis) {
                //直接追加路径进去
                path[curi].push_back(no);   
            }
        }
    }
}

最短路径带一个权值

struct node {
    int no;
    int dis;
    bool operator< (const node &t) const {return dis > t.dis;}
};
vector< vector<node> > road;
int weight[500],w[500],vis[500],path[500],dist[500];
void dijkstra(int c1,int n) {
    const int inf = 0x3f3f3f3f;
    fill(dist,dist + n,inf);
    memset(vis,0,sizeof(vis));
    dist[c1] = 0;
    w[c1] = weight[c1];
    priority_queue<node> qu;
    qu.push(node{c1,0});
    while(!qu.empty()) {
        node r = qu.top(); qu.pop();
        int u = r.no,shortestDis = r.dis,maxW = w[u];
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = 0; i < road[u].size(); i++) {
            int curindex = road[u][i].no;
            int curdis = road[u][i].dis + shortestDis;
            //这里先保存一下最大权值
            int curweight = weight[curindex] + maxW;
            if(dist[curindex] > curdis) {
                dist[curindex] = curdis;
                //这里也就是更新最大权值，和更新最小距离是一个道理
                w[curindex] = curweight;
                path[curindex] = path[u];
                qu.push(node{curindex,dist[curindex]});
            } else if(dist[curindex] == curdis) {
                path[curindex] += path[u];
                //如果最短路径相同，而这时就选择权值最大的路径
                if(w[curindex] < curweight)
                //更新最大权值
                w[curindex] = curweight;
            }
        }
    }
}