dijkstra算法了解+模闆

2017-09-17 21:10:45

writer：pprp

看了看dijkstra算法，用自己語言總結一下主要過程吧，

首先，明确這個算法用處是在于計算單源最短路徑問題并且邊權非負，給出一個起點可以找到其他點的最短路徑

複雜度為O(n^2)

思想：貪心的做法，每次隻看現在的最短路的部分，但是要記得更新已确定該點到其他點的距離

總結一下，dijkstra的做法：

需要 dis vis map 三個數組

給出起點就可以找到到其他所有點的最短路

1、初始化dis數組和起點的dis和vis

2、進行N個點的N次循環

3、從起點開始，找到距離最短的點

4、然後将其dis和vis更改,

5、更改該點相連的其他點的距離

模闆如下：

const int maxn = 1010;
const int INF = 0x3f3f3f3f;
int mp[maxn][maxn];
bool vis[maxn];
int dis[maxn];

void Dijkstra(int st)
{
    for(int i = 1 ; i <= N; i++)//更新dis數組
    {
        dis[i] = mp[st][i];
    }
    vis[st] = 1;
    dis[st] = 0;
    int rec = -1;
    for(int i = 1 ; i < N ; i++)//起到了循環的作用
    {
        Min = INF;
        rec = -1;
        for(int j = 1; j <= N; j++)//找到目前的可以到達的最短距離的點
        {
            if(!vis[j] && Min > dis[j])
            {
                rec = j;
                Min = dis[j];
            }
        }
        if(rec == -1)return ;
        vis[rec] = 1;
        for(int j = 1; j <= N; j++)//更新該點連接配接到的其他的點
        {
            if(!vis[j] && mp[rec][j] != INF && dis[rec] + mp[rec][j] < dis[j])
                dis[j] = mp[rec][j] + dis[rec];
        }
    }
}      

使用方法：

for(int i = 0 ; i < maxn; i++)
        for(int j = 0 ; j < maxn; j++)
            mp[i][j] = INF;
    memset(vis,0,sizeof(vis));
    for(int i = 0 ; i < T ; i++)
    {
        cin >> x >> y >> v;
        if(v < mp[x][y])//去重
            mp[x][y] = mp[y][x] = v;
    }
    Dijkstra(N);
    for(int i = 1; i < N ; i++)
        cout << dis[i] << " ";
    cout << endl;      

代碼改變世界