- #include <iostream>
- using namespace std;
- #define INFINITY 9999999
- #define N 6
- int gety(int lamda[], bool flag[]){//找到Y中的y
- int min=INFINITY;
- int y = -1;
- for(int i=1; i<N; i++){
- if(flag[i] == true)
- if(min>lamda[i]){
- min = lamda[i];
- y = i;
- }
- }
- return y;
- }
- void DIJKSTRA(int g[N][N], int lamda[N]){
- bool flag[] = {false, true, true, true, true, true};//节点i在X中则flag[i] = false,在Y中则flag[i] = true。
- for(int i=0; i<N; i++)
- lamda[i] = g[0][i];
- for(i=1; i<N; i++){
- int y = gety(lamda, flag);
- flag[y] = false;
- for(int j=1; j<N; j++){
- if(flag[j]==true && g[y][j] + lamda[y] < lamda[j]){
- lamda[j] = g[y][j] + lamda[y];
- }
- }
- }
- for(i=0; i<N; i++)
- cout << "源点到顶点" << i+1 << "的距离为:" << lamda[i] << endl;
- }
- void DIJKSTRA_e(int g[N][N], int lamda[N]){
- bool flag[] = {false, true, true, true, true, true};//节点i在X中则flag[i] = false,在Y中则flag[i] = true。
- int zdlj[N][N] = {0};//到每个节点的最短路径过程
- zdlj[0][0] = 1;
- for(int i=0; i<N; i++)
- lamda[i] = g[0][i];
- for(i=1; i<N; i++){
- int k=0;
- int y = gety(lamda, flag);
- flag[y] = false;
- if(zdlj[y][0] == 0){
- zdlj[y][0] = y+1;
- }
- for(int j=1; j<N; j++){
- if(flag[j]==true && g[y][j] + lamda[y] < lamda[j]){
- lamda[j] = g[y][j] + lamda[y];
- for(k=0; k<N; k++){
- if(zdlj[y][k] != 0)
- zdlj[j][k] = zdlj[y][k];
- else{
- zdlj[j][k] = j+1;
- break;
- }
- }
- for(int m=k+1; k<N; k++)
- zdlj[j][m] = 0;
- }
- }
- }
- for(i=0; i<N; i++){
- cout << "源点到顶点" << i+1 << "的距离为:" << lamda[i] << "路径为:1";
- for(int j=0; j<N-1; j++){
- if(zdlj[i][j] != 0)
- cout << "->" << zdlj[i][j];
- }
- cout << endl;
- }
- }
- int main(int argc, char** argv) {
- int lamda[N];
- int g[N][N] = {{0, 1, 12, INFINITY, INFINITY, INFINITY},
- {INFINITY, 0, 9, 3, INFINITY, INFINITY},
- {INFINITY, INFINITY, 0, INFINITY, 5, INFINITY},
- {INFINITY, INFINITY, 4, 0, 13, 15},
- {INFINITY, INFINITY, INFINITY, INFINITY, 0, 4},
- {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 0}
- };
- DIJKSTRA(g, lamda);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0106201512722.html
来源: http://www.codesnippet.cn/detail/0106201512722.html