转载

迪杰斯特拉算法

迪杰斯特拉算法

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。注意该算法要求图中不存在负权边。

算法过程

  • 初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则minDis(u,v)有权重,否则为无穷大
  • 从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。
  • 以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。
  • 重复步骤b和c直到所有顶点都包含在S中。

对如下连通图求单源点路径

C++代码

#include<iostream>
#include<limits.h> 
using namespace std;

/*图是连通图*/ 
int a[6][6] = {
    {0, 7, 9, INT_MAX, INT_MAX, 14},
    {7, 0, 10, 15, INT_MAX, INT_MAX},
    {9, 10, 0, 11, INT_MAX, 2},
    {INT_MAX, 15, 11, 0, 6, INT_MAX},
    {INT_MAX, INT_MAX, INT_MAX, 6, 0, 9},
    {14, INT_MAX, 2, INT_MAX, 9, 0}
};

int main() {
    int minDis[6]; /*存储最短距离*/ 
    for(int i = 0; i < 6; i++) minDis[i] = a[0][i];

    bool visited[6]; /*标记数组*/
    for(int i = 0; i < 6; i++) visited[i] = false;

    visited[0] = true; /*源点加入*/ 
    /*循环n-1次*/
    for(int i = 1; i < 6; i++) {

        /*找出最小距离点*/
        int min = INT_MAX;
        int w = 0;
        for(int j = 1; j < 6; j++) {
            if(visited[j]) continue;
            if(minDis[j] < min) {
                min = minDis[j];
                w = j;
            }
        }

        /*更新距离*/
        visited[w] = true;
        for(int j = 1; j < 6; j++) {
            if(visited[j] || a[w][j]==INT_MAX) continue;

            if(minDis[w] + a[w][j] < minDis[j]) minDis[j] = minDis[w] + a[w][j];
        } 
    }

    for(int i = 0; i < 6; i++) {
        printf("%d ", minDis[i]);
    }
    return 0;
} 
/*0 7 9 20 20 11*/
正文到此结束
本文目录