今天开始学算法系列---Dijkstra

    Dijkstra算法是求单源最短路径好方法，但是只能处理没有负边的图的问题，有一条边为负的就会导致最终的结果不正确
   时间复杂度可以达到O(|E|log|v|)， 所以一般求单源最短路径问题都可以用这个算法
   伪代码：
   priority_queue que;
   que.push(startV);
   while que is not empty
        V a = que.top();
          que.pop();
        for all V connect with a:
            if d(v) > d(a) + length_a_to_v;
               d(v) = d(a) + length_a_to_v;
               que.push(v);

    直接上代码：
    

#include <functional>
#include <queue>
using namespace std;
#define MAXV 4
#define INF 100000
int d[4] = { 0 };
int edge[4][4] = { 0 };
void init()
{
    for (int i = 0; i < MAXV; i++)
        for (int j = 0; j < MAXV; j++)
            edge[i][j] = INF;
    edge[0][0] = 0;
    edge[0][1] = 6;
    edge[0][2] = 1;
    edge[1][3] = 2;
    edge[2][3] = 8;
    edge[3][0] = 3;
}

typedef pair<int, int> p;



void dijsktra(p s)
{
    priority_queue<p, vector<p>, greater<p>> que;
    que.push(s);
    while (!que.empty())
    {
        p tmp = que.top();
        que.pop();
        for (int i = 0; i < MAXV; i++)
        {
            if (tmp.first != i)
            {
                if (edge[tmp.first][i] != INF && (d[i] > d[tmp.first] + edge[tmp.first][i]))
                {
                    d[i] = d[tmp.first] + edge[tmp.first][i];
                    p newP;
                    newP.first = i;
                    newP.second = d[i];
                    que.push(newP);
                }
            }
        }

    }
    for (int i = 0; i < MAXV; i++)
    {
        printf("%d",d[i]);
    }

}

int _tmain(int argc, _TCHAR* argv[])
{
    fill(d, d + 4, INF);

    init();
    d[0] = 0;
    p s;
    s.first = 0;
    s.second = d[0];
    dijsktra(s);

    return 0;
}