算法的思想如下：
規(guī)定一個 出發(fā)點宙攻，然后先初始化距離數(shù)組彻亲。數(shù)組中的每個下標(biāo)就對應(yīng)一個結(jié)點兵拢，每個數(shù)據(jù)項就是出發(fā)點到每個結(jié)點的距離翻斟。
1:將一個集合分為兩部分，一個是已經(jīng)找過的結(jié)點U卵佛，一個是沒有找到過的v
2:在距離的數(shù)組中杨赤，沒有訪問過的結(jié)點中找一個權(quán)重最小的邊敞斋，然后將這個結(jié)點添加到u中截汪，并且以這個結(jié)點作為中間結(jié)點，來更新數(shù)組植捎，判斷條件是i到temp+temp到j(luò) 的距離是不是小于i到j(luò)的距離衙解，若是，則就要更新焰枢。
3:直到u中的結(jié)點的個數(shù)=圖中的結(jié)點的個數(shù)
算法的實現(xiàn)其實還是比較簡單蚓峦，和prim算法圖的prim算法沒什么差別，都是維護(hù)一個距離數(shù)組济锄，來更新數(shù)組暑椰，不同的是只是添加一個判斷條件而已。荐绝，在這里就沒什么可說的一汽，不懂的分析程序，運行結(jié)果一兩遍就基本明白了
程序如下：
//
// main.cpp
// dijkstra
//
// Created by 橘子和香蕉 on 2018/12/2.
// Copyright ? 2018 橘子和香蕉. All rights reserved.
//
/*
其實思想和之前的prim算法一樣，還是分為兩個集合召夹，一個是訪問過的u岩喷，一個是訪問過的v，找一個中間結(jié)點监憎，判斷 i到j(luò)的距離和i到temp+demp到j(luò)的距離那個短纱意，更新就好。
還是要維護(hù)一個距離的數(shù)組鲸阔，在沒有訪問過的結(jié)點中每次找一個最小的邊偷霉，同時也就是找到了v的結(jié)點，添加到u中褐筛，然后以這個結(jié)點為中間結(jié)點來更新距離數(shù)組腾它，判斷i到j(luò)的距離和i到temp+demp到j(luò)的距離，
f
*/
#include <iostream>
using namespace std;
#define MAX 9999//用9999來表示不可到達(dá)死讹。為什么不用之前的INT_MAX瞒滴，因為在之后的距離的更新會產(chǎn)生問題。INT_MAX是int的最大值赞警，在加就會導(dǎo)致胃負(fù)數(shù)妓忍，這就產(chǎn)生了問題
typedef struct node{
char data;//數(shù)據(jù)域
int isAccess;//用來標(biāo)記是否被訪問過
}node;
#define VERTEXNUM 100
class Graph{
private:
node vertex[VERTEXNUM];//頂點表
int edge[VERTEXNUM][VERTEXNUM];//邊表
int vertexNum;//頂點個數(shù)
int edgeNum;//邊的個數(shù)
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];//定義一個中間數(shù)組
int temp = -1;//定義中間結(jié)點
int position = locate(data);
vertex[position].isAccess = true;
//初始化distince數(shù)組
for (int i = 0; i<vertexNum; i++) {
if( edge[position][i] < MAX ){
distince[i] = edge[position][I];
}else{
distince[i] = MAX;
}
}
int minVertexNum = 0;//定義結(jié)點個數(shù)
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<<"到每個結(jié)點的最短距離如下"<<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;
}
測試的圖如下：
在這里用的是臨接矩陣來實現(xiàn)無向圖；
image.png
運行結(jié)果如下：
image.png
