dijkstra（单源最短路）

dijkstra由于是贪心的，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径。但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin’），再通过这个负权边L(L<0)，使得路径之和更小（dmin’+L<dmin）,则dmin’+L成为最短路径，并不是dmin，这样dijkstra就被囧掉了。
比如n=3，邻接矩阵：
0，3，4
3，0，-2
4，-2，0
用dijkstra求得d[1，2]=3，事实上d[1，2]=2，就是通过了1-3-2使得路径减小。

寻找单源最短路，且边权为正（SSSP）（一个源点到各个顶点）

每次找到离原点最近的一个顶点（除了已经被标记过之外的），然后以该顶点为中心进行扩展，最终得到原点到其余所有点的最短路径。

//简单来说，就是找到所有n-1个点，然后去更新状态，当然有可能用当前最近点（除标记外）去更新后的值仍不变。
for(int i = 1; i < n; i++){//n-1次 
    min = inf;
    for(int j = 1; j <= n; j++){
        if(book[j] == 0 && dis[j] < min){
            min = dis[j];//dis保存距离（离源点） 
            u = j;//u为离源点最近的顶点 
        }
        book[u] = 1;//标记，走过的点不会再是后面点的中转 
        for(int k = 1; k <= n; k++){
            if(dis[k] < inf){//概念上防止无穷与无穷相比较 
                if(dis[k] > dis[u] + e[u][k])//如果遍历到的点原来的路程大于中转路程 
                    dis[k] = dis[u] + e[u][k];//将该点原来的路程更新 
            }
        }
    }
}

多贴个版本

const int INF = 999999999; 
int main(){
    memset( v , 0 , sizeof(v));  //初始化标记数组 
    for(int i = 0; i < n; i++) d[i] = (i == 0? 0 : INF);  //初始化路径大小，设源点到其他点的路长均为INF 
    for(int i = 0; i < n; i++){//一次循环找到一个点 
        int x, m = INF;      // 声明x，为m设置INF初始值 
        for(int y = 0; y < n ; y++ )   //在所有未标记的节点中
                     if(!v[y] && d[y] <= m) m = d[x=y];  //找到离源点最近的点 
        v[x] = 1;              //标记走过的点 
        for(int y = 0; y < n; y++) //对于从x出发的所有边（x，y）
                     d[y] = min(d[y] , d[x] + w[x][y]); //更新源点到该点的距离 
    }
    
    return 0;
}

对于这个算法，一开始理解得很模糊，后来又以为是按照一维一维的顺序一直搜索下去，但实际上算法很简单，只要按照d的大小进行遍历就可以，并不存在其他的因素，最外层循环仅仅确定层数，并不作为索引

优先队列优化：

const int INF = 0x3f3f3f3f;
const int MAXN=1000010;
struct qnode      //优先队列的创建（储存节点v以及到源点的距离C）
{
    int v;//节点v
    int c;//源点的距离（用来排序）
    qnode(int _v=0, int _c=0):v(_v),c(_c){}  //初始化为0？？？
    bool operator<(const qnode &r)const//定义优先队列的排序方式（实际上可以用pair进行替代），先比较第一维，相等时比较第二维 
    { return c>r.c;}
};

struct Edge//边结构
{
    int v,cost;    //储存边以及权  
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}//初始化？？？
};
vector<Edge>E[MAXN];//看作二维数组，每个i数组储存着从i点到下一边的所有数据
bool vis[MAXN];//标记数组
int dist[MAXN];//离源点的距离
void Dijkstra(int n, int start)     //点的编号从1开始，n是点的个数，start是源点
{
    memset(vis, false, sizeof(vis));//初始化标记数组
    for(int i = 1; i <= n;i++)dist[i] = INF;//初始化距离数组
    priority_queue<qnode>que;//创建定义的优先队列，类型为qnote
    while(!que.empty()) que.pop();//清空队列（这里不明白为什么要清空，是赋了初值吗？那为什么要赋初值）
    dist[start]=0;//源点到源点的距离初始化为0，以便于得出后续
    que.push(qnode(start,0));//源点入队，距离为0
    qnode tmp;//qnode类型的中转变量
    while(!que.empty()){//只要队列不为空，也可以看作每次出队都是一轮松弛
        tmp=que.top();//将队列中d最小的赋给tmp
        que.pop();//出队
        int u = tmp.v;//方便后续的操作，令u=该点的序号
        if(vis[u])continue;//如果已被标记，那么跳过
        vis[u]=true;//标记
        for(int i=0;i<E[u].size();i++){//循环u的下一点的个数次 
            int v=E[tmp.v][i].v;//v=（点u数组中的下一点） 
            int cost=E[u][i].cost; //cost = （点u数组中到下一点的距离） 
            if(!vis[v]&&dist[v]>dist[u]+cost){ //松弛操作
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));//入队
            }
        }
    }
}

void addedge(int u,int v,int w){
    E[u].push_back(Edge(v,w));
}