c++ 实现dijkstra算法与floyed算法

ゝ一世哀愁。 2023-06-17 13:52 11阅读 0赞

# 1 算法原理 #

将图使用邻接矩阵表示，如下图所示，其中 a i j a\_\{ij\} aij表示第 i i i个节点到第 j j j个节点的距离。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ4MzM4MQ_size_14_color_FFFFFF_t_70]

##### dijkstra的更新方法： #####

注意，dijkstra更新的是一个向量，所以dijkstra称为单源最短路径。  
 a k j n = m i n \{ a k j n − 1 , a k n n − 1 + a n j n − 1 \} a\_\{kj\}^n=min\\\{a\_\{kj\}^\{n-1\},a\_\{kn\}^\{n-1\}+a\_\{nj\}^\{n-1\}\\\} akjn=min\{ akjn−1,aknn−1\+anjn−1\}  
其中k为指定的一个源(点)， a k j n a\_\{kj\}^n akjn为一个向量。这里面 n n n的选取并不是按照顺序的，而是选择前一时刻向量中距离值最小，并且没有当过跳板的点，作为这一时刻的跳板 n n n。

##### floyed的更新方法： #####

注意，floyed算法更新的是整个邻接矩阵矩阵  
![在这里插入图片描述][20191129110956856.png]  
 a i j n a\_\{ij\}^n aijn是一个矩阵，并且 n n n的选取并没有规矩，就是按顺序选取的。因此更新起来也比较方便。

##### 两个算法的比较 #####

乍一看似乎floyed可以解决的问题包括了dijtstra,甚至还能求出多余的问题的解。抛开两种算法提出的时间顺序，这两者的最大差异在于时间复杂度上。相同条件下求解单源最短路径问题，dijkstra优于floyed，这种优势在大规模搜索策略中十分明显。

# 2 程序源码 #

程序使用VS2017编译运行成功，运行时间很快。程序编写过程中修改很多次dijkdstra算法的实现，因为它有很多细节需要注意。  
相比于dijkstra算法，floyed算法较为容易实现。

#include<iostream>
    #include<algorithm>
    using namespace std;
    constexpr int inf = 9999;  // 模拟无穷大
    
    // 使用邻接矩阵将图存储
    // -1代表距离为无穷
    int graph[7][7] = { 
    	inf, 2, inf, 4, inf, inf, inf,
    	inf,inf, 4,  inf, 5, inf,  inf,
    	inf,inf,inf,  inf, inf, inf, 10,
    	inf,inf,inf,inf,4,inf,inf,
    	inf,inf,2,inf,inf,4,inf,
    	inf,inf,inf,inf,inf,inf,inf,
    	inf,inf,inf,inf,inf,6,inf
    };
    
    int *get_index(int *arr, int arr_len, int value) { 
    	int res[7] = { -1,-1,-1,-1,-1,-1,-1};
    	int i = 0;
    	for (int j = 0; j < arr_len; j++) { 
    		if (arr[j] == value) { 
    			res[i] = j;
    			i++;
    		}
    	}
    	return res;
    }
    
    // Dijkstra算法
    // 求第n个节点的最短路径，直接打印出来
    void dijkstra(int m) { 
    	cout << "使用dijtstra算法求节点" << m << "到其他节点的最短路径：" << endl;
    	int n = m - 1;
    	int distance[7] = { };
    	int distance_temp[7] = { };
    	int temp[7] = { };
    	int j;
    	int is_visited[7] = {  0,0,0,0,0,0,0 };
    	int is_visited2[7] = {  0,0,0,0,0,0,0 };
    	for (int i = 0; i < 7; i++) { 
    		distance[i] = graph[n][i];
    		distance_temp[i] = graph[n][i];
    	}
    	for (int p = 0; p < 7; p++) { 
    		j = -2;
    		int min = *min_element(distance_temp, distance_temp + 7);  // 每次找最小值
    	
    		if (min > 9998) {   //最小值为无穷时退出循环
    			break;
    		}
    		int *res = get_index(distance, 7, min);
    		for (int i = 0; i < 7; i++) { 
    			if (res[i] == -1) {  break; }
    			if (is_visited[res[i]] == 0) { 
    				j = res[i];
    				is_visited[j] = 1; // 标记访问过的点
    				break;
    			}
    		}
    
    		if (j == -2) {  break; }
    		is_visited2[j] = 1;
    
    		if (j == n) { 
    			continue;
    		}
    		for (int k = 0; k < 7; k++) { 
    			int distance_nj = distance[j];
    			temp[k] = distance_nj + graph[j][k];
    		}
    		// 比较temp与distance
    		for (int i = 0; i <7; i++) { 
    			if (temp[i] < distance[i]) { 
    				distance[i] = temp[i];
    			}
    		}
    		for (int u = 0; u < 7; u++) { 
    			if (is_visited2[u] != 0) { 
    				distance_temp[u] = inf;
    			}
    			else { 
    				distance_temp[u] = distance[u];
    			}
    		}
    	}
    	for (int i = 0; i < 7; i++) { 
    		if (distance[i] > 9998) { 
    			if (i == n) { 
    				cout << "distance from " << m << " to " << i + 1 << " is 0" << endl;
    			}
    			else { 
    				cout << "distance from " << m << " to " << i + 1 << " is infinite" << endl;
    			}
    		}
    		else { 
    			cout << "distance from " << m << " to " << i + 1 << " is " << distance[i] << endl;
    
    		}
    	}
    }
    
    // Floyed算法
    void floyed() { 
    	cout <<endl << "floyed算法:" << endl;
    	int result[7][7] = { };
    	for (int i = 0; i < 7; i++) { 
    		for (int j = 0; j < 7; j++) { 
    			if (i == j) { 
    				result[i][j] = 0;
    			}
    			else { 
    				result[i][j] = graph[i][j];
    			}
    			
    		}
    	}
    	for (int n = 0; n < 7; n++) { 
    		for (int i = 0; i < 7; i++) { 
    			for (int j = 0; j < 7; j++) { 
    				if (result[i][j] > result[i][n] + result[n][j]) { 
    					result[i][j] = result[i][n] + result[n][j];
    				}
    			}
    		
    		}
    	}
    	for (int i = 0; i < 7; i++) { 
    		for (int j = 0; j < 7; j++) { 
    			if (result[i][j] > 9998) { 
    				cout << " inf ";
    			}
    			else { 
    				cout <<" "<< result[i][j]<<" ";
    			}
    		}
    		cout << endl;
    	}
    }
    
    int main() { 
    	// 使用的图如上述graph所示 7*7的矩阵表示7个节点的图
    	// 第一个节点用1表示，不用0
    	dijkstra(1);
    	floyed();
    	system("pause");
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ4MzM4MQ_size_14_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191129110029659.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ4MzM4MQ==,size_14,color_FFFFFF,t_70
[20191129110956856.png]: https://img-blog.csdnimg.cn/20191129110956856.png