算法的思想如下：
规定一个 出发点，然后先初始化距离数组。数组中的每个下标就对应一个结点，每个数据项就是出发点到每个结点的距离。
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
