适用范围：

不含负权值边的图

---

 

基本代码

思路：从点出发，循环至多N次。每一次在当前已知可达路径中选 到达取路径长度 最小且未被访问过得点作为这一次的起点，再遍历该点的邻接点，更新到达路径长度。

//邻接矩阵方式 #include 
     
      using namespace std;const int maxn = 3000 + 10;const int INF = 0x3f3f3f3f;int n, m, st; //n:顶点数  m:边数  st:源点int dist[maxn]; //dist[i]:从st到i的当前最短路径长度int path[maxn]; //path[i]:st到i的最短路径上的前一个点int g[maxn][maxn];bool visited[maxn]; //顶点i是否被访问过void Dijsktra(){    //初始化 vis  dist  path    memset(visited, false, sizeof(visited));    for(int i = 0; i < n; i++) dist[i] = INF;    dist[st] = 0;    path[st] = -1;        //循环n次    for(int k = 0; k < n; k++){        //1 先找到dist中最小的 且i未被访问的顶点 记录下来作为出发点        int Min = INF;        int pos;        for(int i = 0; i < n; i++){            if(!visited[i] && dist[i] < Min){                Min = dist[i];                pos = i;            }        }            //2 再以该点为出发点 访问其邻接点 计算和更新        visited[pos] = true;        for(int i = 0; i < n; i++){            if(!visited[i] && g[pos][i] != INF && (Min + g[pos][i] < dist[i])){                dist[i] = Min + g[pos][i];                path[i] = pos; //记录来自哪一个顶点            }        }    }}void showPath(int ed){    //一直向前寻找直到结束    int i = ed;    printf("%d ",ed);    while(path[i] != -1){        printf("%d ",path[i]);        i = path[i];    }    printf("\t-->dis : %d\n",dist[ed]);}int main(){    while(~scanf("%d%d%d", &n, &m, &st)){                //初始化图        for(int i = 0; i < n; i++){            for(int j = 0; j < n; j++){                g[i][j] = INF;            }            g[i][i] = 0;        }                //构建图        for(int i = 0; i < m; i++){            int a, b, c;            scanf("%d%d%d",&a, &b, &c);            g[a][b] = c;        }        Dijsktra();        for(int i = 0; i < n; i++){            printf("%d-->%d : ", st, i);            showPath(i);        }    }    return 0;}
     

 

//邻接矩阵方式#include 
     
      using namespace std;const int maxn = 3000 + 10;const int INF = 0x3f3f3f3f;struct edge{    int to, cost;};typedef pair
      
        P;int n, m;int d[maxn];int path[maxn];bool visited[maxn];vector
       
         G[maxn];void dijsktra(int s, int V){    priority_queue
        
         , greater
         
 > que;    for(int i = 0; i < V; i++) d[i] = INF;    memset(visited, 0, sizeof(visited));    d[s] = 0;    que.push(P(0, s));    while(!que.empty()){        P p = que.top(); que.pop();        int v = p.second;        if(d[v] < p.first) continue;        for(int i = 0; i < G[v].size(); i++){            edge e = G[v][i];            if(d[e.to] > d[v] + e.cost){                d[e.to] = d[v] + e.cost;                que.push(P(d[e.to], e.to));            }        }    }}int main(){    int st;    while(~scanf("%d%d%d", &n, &m, &st)){        for(int i = 0; i < n; i++) G[i].clear();        for(int i = 0; i < m; i++){            edge e; int a;            scanf("%d%d%d",&a, &e.to, &e.cost);            G[a].push_back(e);        }        dijsktra(st, n);        for(int i = 0; i < n; i++) printf("%d ",d[i]);        printf("\n");    }    return 0;}
        
       
      
     

 

---

 

拓展1：边上增加花费属性，求最小花费最短路（路径记录则同上）

//修改第二个For循环//value[i] 到顶点i的所有边的总花费 初始值为INF//cost[i][j] 边i-j的花费for(int i = 0; i < n; i++){    if(!visited[i] && g[pos][i] != INF){        if(Min + g[pos][i] < dist[i]){            dist[i] = dist[i] + g[pos][i];            value[i] = value[pos] + cost[u][v];        }else if(Min + g[pos][i] == dist[i] && value[pos] + cost[pos][i] < value[i]){            value[i] = value[pos] + cost[pos][i];        }    }}

 

---

 

拓展2：顶点上增加花费属性，求最小花费最短路（同拓展一，仅修改cost为一维）

//修改第二个For循环//value[i] 到顶点i的所有经过顶点的总花费(包括点i) 初始值为INF//cost[i] 顶点i的花费for(int i = 0; i < n; i++){    if(!visited[i] && g[pos][i] != INF){        if(Min + g[pos][i] < dist[i]){            dist[i] = dist[i] + g[pos][i];            value[i] = value[pos] + cost[i];        }else if(Min + g[pos][i] == dist[i] && value[pos] + cost[i] < value[i]){            value[i] = value[pos] + cost[i];        }    }}

 

---

 

拓展3：求最短路径条数

//修改第二个For循环//num[i] = 0, num[st] = 1  num[i]从st到i的最短路径条数for(int i = 0; i < n; i++){    if(!visited[i] && g[pos][i] != INF){        if(Min + g[pos][i] < dist[i]){            dist[i] = dist[i] + g[pos][i];            num[i] = num[pos];        }else if(Min + g[pos][i] == dist[i]){            num[i] = num[i] + num[pos];        }    }}

 

---

 

综合以上拓展中2~3个 例如：求顶点花费最大的最短路路径和其个数。

//修改第二个For循环for(int i = 0; i < n; i++){    if(!visited[i] && g[pos][i] != INF){        if(Min + g[pos][i] < dist[i]){            dist[i] = dist[i] + g[pos][i]; //更新路径长度            value[i] = value[pos] + cost[i]; //更新顶点花费            num[i] = num[pos]; //统计数量            path[i] = pos; //记录路径        }else if(Min + g[pos][i] == dist[i]){            num[i] = num[i] + num[pos];            if(value[i] < value[pos] + cost[i]){                value[i] = value[pos] + cost[i];                path[i] = pos;            }        }    }}

 

---

 待理解。。。

用vector把dijkstra的path记录下来（包括）

//path[i]:顶点i可以来自的最短路来源集合vector
     
       path[maxn];// ...//修改第二个For循环if(Min + g[pos][i] < dist[i]){    dist[i] = dist[pos] + g[pos][i];    path[i].clear();    path[i].push_back(pos);} else if(Min + g[pos][i] == dist[i]){    path[i].push_back(pos);}
     

//然后处理