Dijkstra算法求最短路

Dijkstra算法和Prim算法具有极其相似的地方，二者都是构建两个集合，利用贪心算法，将其中一个集合不断进行扩充，最终求得最优解。

算法实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MAX_N = 1000, INF = 0x7ffffff;
int adj[MAX_N + 1][MAX_N + 1];
int distance[MAX_N + 1];
double minD[MAX_N + 1], graph[MAX_N][MAX_N];
bool visited[MAX_N + 1];
int t, n;
typedef pair<double, int> P;
double Dijkstra(int s, int len){
    priority_queue<P, vector<P>, greater<P> > q;
    fill(minD, minD + MAX_N, INF);
    memset(visited, false, sizeof visited);
    minD[s] = 0;
    q.push(P(minD[s], s));
    while(!q.empty()){
        P front = q.top();
        q.pop();
        int u = front.second;
        if(visited[u]) continue;
        visited[u] = true;
        for(int v = 1; v <= len; ++v){
            if(minD[u] + graph[u][v] < minD[v]){
                minD[v] = minD[u] + graph[u][v];
                q.push(P(minD[v], v));
            }
        }
    }
    for (int i = 1; i <= len; i++) printf("%d ", minD[i]);
}