[算法]dijstra算法-单个源点到其他顶点的最短路径问题

浏览数：67 / 时间：2015年06月09日

近来在重新温习图论算法，不是那么容易实现，很多细节没有扣紧，dijstra的算法不是难，但是我只记得大概，要独立实现算法，我还真的忘记了，还得看了看算法导论才记得如何做。

其实dijstra算法是一个贪心算法，

1、每一次从候选集Q中选择距离源点最近的一个点candidate，加入已选集S，

2、通过candidate为中转点，如果经过candidate中转之后，源点与候选集Q的点的距离变小，则源点与候选集的点的距离。

3、重复1，2直至所有点归入S中。

大概算法是如此，更多细节是代码的实现当中。

#include <iostream>
using namespace std;
const int maxSize = 10;
const int infinite = 9999;
void dijkstra(const int map[maxSize][maxSize],int p[maxSize], int d[maxSize], int n, int s)
{   //map为邻接矩阵，p为存储最短路径终点的路径前驱，d存储源到各点的最短距离
    bool *selected = new bool[n];
    int numSelected = 0;//已经找到最短路径的点的个数，不包含源自身 
    for(int i = 0; i < n; ++i)//初始化p与d 
    {
        selected[i] = false;//刚刚开始所有点都未被找到最短路径 
        d[i] = map[s][i];
        if(d[i] < infinite)
        {
            p[i] = s;
        }
        else
        {
            p[i] = -1;
        }
    }
    selected[s] = true;//源点初始化为已经找到最短路径就是自身到自身，距离为0 
    p[s] = -1; //源点没有路径前驱，初始化为-1； 
    int candidate, min, i;
    while(numSelected < n-1)
    {
        min = infinite;
        for(i = 0; i < n; ++i)//此循环找到候选点集Q中（未找到最短路径的点）离源点s最近的点candidate 
        {
            if(!selected[i] && d[i] < min)
            {
                min = d[i];
                candidate = i;
            }
        }
        for(i = 0; i < n; ++i)//此循环更新已入选的点集S（已找到最短路径的点）与候选点集Ｑ中的点的距离 
        {
            if(i != s && !selected[i] && d[i] > d[candidate] + map[candidate][i])
            {
                d[i] = d[candidate] + map[candidate][i];
                p[i] = candidate;
            }
        }
        selected[candidate] = true;
        ++numSelected;
    }
    delete [] selected;
}

void printPath(int p[maxSize],int s,int des)
{
    int st[maxSize],top = -1, t = des;
    while(-1 != t)
    {
        st[++top] = t;
        t = p[t];
    }
    while(top >0)
    {
        cout<<st[top--]<<"->";
    }
    cout<<st[top];
}

int main()
{ 
    int map[maxSize][maxSize]={{0,5,infinite,infinite,7},
                                {5,0,4,2,infinite},
                                {infinite,4,0,6,8},
                                {infinite,2,6,0,1},
                                {7,infinite,8,1,0}};

    int p[maxSize],d[maxSize];
    dijkstra(map,p,d,5,0);
    for(int i = 0; i < 5; ++i)
    {
        cout<<"min distance of 0 to "<<i<<" is "<<d[i]<<endl;
        cout<<"paht is ";printPath(p,0,i);
        cout<<endl;    
    }
}