算法的思想如下:
规定一个 出发点, 然后先初始化距离数组. 数组中的每个下标就对应一个结点, 每个数据项就是出发点到每个结点的距离.
1: 将一个集合分为两部分, 一个是已经找过的结点 U, 一个是没有找到过的 v
2: 在距离的数组中, 没有访问过的结点中找一个权重最小的边, 然后将这个结点添加到 u 中, 并且以这个结点作为中间结点, 来更新数组, 判断条件是 i 到 temp+temp 到 j 的距离是不是小于 i 到 j 的距离, 若是, 则就要更新.
3: 直到 u 中的结点的个数 = 图中的结点的个数
算法的实现其实还是比较简单, 和 prim 算法图的 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 <iostream>
- using namespace std;
- #define MAX 9999// 用 9999 来表示不可到达. 为什么不用之前的 INT_MAX, 因为在之后的距离的更新会产生问题. INT_MAX 是 int 的最大值, 在加就会导致胃负数, 这就产生了问题
- typedef struct node{
- char data;// 数据域
- int isAccess;// 用来标记是否被访问过
- }node;
- #define VERTEXNUM 100
- class 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<<endl;
- cout<<endl;
- cout<<"顶点边:\n";
- cout<<"vertexNum:"<<vertexNum<<"edgeNum:"<<edgeNum<<endl;
- for (int i = 0; i<vertexNum; i++) {
- cout<<vertex[i].data<<"\t";
- }
- cout<<endl;
- cout<<"边表如下:\n";
- for (int j = 0; j<vertexNum; j++) {
- for (int k = 0; k<vertexNum ; k++) {
- cout<<edge[j][k]<<"\t";
- }
- cout<<endl;
- }
- }
- int Graph::locate(char data){
- for (int i = 0; i<vertexNum;i++) {
- if(vertex[i].data == data){
- return I;
- }
- }
- return -1;
- }
- Graph::Graph(int vertexNum,int edgeNum){
- this->vertexNum = vertexNum;
- this->edgeNum = edgeNum;
- initEdge();
- }
- void Graph::create(){
- cout<<"input Graph data\n";
- for (int i = 0; i<vertexNum; i++) {
- cin>>vertex[i].data;
- vertex[i].isAccess = false;
- }
- char start ,end;
- int wieght = -1;
- for (int j = 0; j<edgeNum; j++) {
- cout<<"input start and end of edge:\n";
- cin>>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<vertexNum; i++) {
- for (int j =0 ; j<=i; j++) {
- edge[i][j] = MAX;
- edge[j][i] = MAX;
- }
- }
- }
- void Graph::dijkstra(char data){
- int distince[100];// 定义一个中间数组
- int temp = -1;// 定义中间结点
- int position = locate(data);
- vertex[position].isAccess = true;
- // 初始化 distince 数组
- for (int i = 0; i<vertexNum; i++) {
- if( edge[position][i] < MAX ){
- distince[i] = edge[position][I];
- }else{
- distince[i] = MAX;
- }
- }
- int minVertexNum = 0;// 定义结点个数
- while (minVertexNum != vertexNum-1) {
- int min = MAX;
- for (int i = 0; i<vertexNum; i++) {
- if( vertex[i].isAccess == false && distince[i] < min){
- min = distince[I];
- temp = I;
- }
- }
- vertex[temp].isAccess = true;
- for (int i = 0; i<vertexNum; i++) {
- if((vertex[i].isAccess == false) && ( distince[temp]+edge[temp][i] < distince[i]) ){
- distince[i] = distince[temp]+edge[temp][I];
- }
- }
- minVertexNum++;
- }
- cout<<"到每个结点的最短距离如下"<<endl;
- for (int i = 0; i<vertexNum; i++) {
- cout<<vertex[i].data<<":"<<distince[i]<<"\n";
- }
- }
- int main(){
- Graph a(6,8);
- a.create();
- a.printGraph();
- cout<<endl;
- a.dijkstra('1');
- return 1;
- }
测试的图如下:
在这里用的是临接矩阵来实现无向图;
image.PNG
运行结果如下:
image.PNG
来源: http://www.jianshu.com/p/7ecdc1a8abe4