图的最短路径—— dijkstra算法-白红宇

算法的思想如下：

规定一个出发点，然后先初始化距离数组。数组中的每个下标就对应一个结点，每个数据项就是出发点到每个结点的距离。

1:将一个集合分为两部分，一个是已经找过的结点U，一个是没有找到过的v

2:在距离的数组中，没有访问过的结点中找一个权重最小的边，然后将这个结点添加到u中，并且以这个结点作为中间结点，来更新数组，判断条件是i到temp+temp到j 的距离是不是小于i到j的距离，若是，则就要更新。

3:直到u中的结点的个数=图中的结点的个数

算法的实现其实还是比较简单，和prim算法没什么差别，都是维护一个距离数组，来更新数组，不同的是只是添加一个判断条件而已。，在这里就没什么可说的，不懂的分析程序，运行结果一两遍就基本明白了

程序如下：

////  main.cpp//  dijkstra////  Created by 橘子和香蕉 on 2018/12/2.//  Copyright © 2018 橘子和香蕉. All rights reserved.///*  其实思想和之前的prim算法一样，还是分为两个集合，一个是访问过的u，一个是访问过的v，找一个中间结点，判断 i到j的距离和i到temp+demp到j的距离那个短，更新就好。 还是要维护一个距离的数组，在没有访问过的结点中每次找一个最小的边，同时也就是找到了v的结点，添加到u中，然后以这个结点为中间结点来更新距离数组，判断i到j的距离和i到temp+demp到j的距离， f */#include 
    
     using namespace std;#define MAX 9999//用9999来表示不可到达。为什么不用之前的INT_MAX，因为在之后的距离的更新会产生问题。INT_MAX是int的最大值，在加就会导致胃负数，这就产生了问题typedef struct node{    char  data;//数据域    int isAccess;//用来标记是否被访问过}node;#define VERTEXNUM 100class Graph{private:    node  vertex[VERTEXNUM];//顶点表    int edge[VERTEXNUM][VERTEXNUM];//边表    int vertexNum;//顶点个数    int edgeNum;//边的个数                int locate(char  data);//在顶点表中找data的位置    void initEdge();    public:    Graph(int vertexNum,int edgeNum);    void create();    void dijkstra(char data);    void printGraph();//输出};void Graph::printGraph(){    cout<
     
      vertexNum = vertexNum;    this->edgeNum = edgeNum;    initEdge();}void Graph::create(){    cout<<"input Graph data\n";    for (int i = 0; i
      
       >vertex[i].data;        vertex[i].isAccess = false;    }    char start ,end;    int wieght = -1;    for (int j = 0; j
       
        >start>>end>>wieght;        int startPosition = locate(start);        int endPosition = locate(end);        edge[startPosition][endPosition] = wieght;        edge[endPosition][startPosition] = wieght;    }    }void Graph:: initEdge(){    for (int i = 0;  i

测试的图如下：

在这里用的是临接矩阵来实现无向图；

运行结果如下：