Dijkstra算法实现非负权值最短路径的求解(另用小根堆进行优化)
利用Dijkstra算法求解非负权值的最小值，基本思想是，进行n-1轮的循环，每一轮都是：求出单边条件下起始结点v0到其他各结点的最短距离，并将邻接到的这个点v1标为“已处理过”，然后再以v1作为中转，找到跟v1距离最近的剩下的顶点v2，接着比较dist[v2]的值和dist[v1]+weight[v1][v2]，如果dist[v2]较大，则将dist[v2]改写为dist[v1]+weight[v1][v2]。
基本实现如下：
#include <iostream>#include <memory.h>using namespace std;/***************************堆**********************/struct Heap{int link; //表示初始结点临接到的顶点int dist;//权值} heap[60];//下滑操作void siftDown(int start,int end){//将start号结点向下调整直到endint i=start,j=2*i;heap[0]=heap[i]; //用heap[0]来临时保存i结点的值while(j<=end){//有右孩子并且右孩子比左孩子小时，或者当优先级相同并且j号结点后出现时将j保存右孩子if(j<end&&heap[j].dist>heap[j+1].dist) ++j;//比j号结点小时，不需调整if(heap[0].dist<heap[j].dist)break;else{//向下调整heap[i]=heap[j];i=j;j=2*j;}}heap[i]=heap[0];}//向上调整的函数//将结点start调整到根结点1为止void siftUp(int start){int j=start,i=j/2;heap[0]=heap[j];while(j>0){//优先级相同时，numID小的先输出if(heap[i].dist<heap[0].dist)break;else{//向上调整工作heap[j]=heap[i];j=i;i=i/2;}}heap[j]=heap[0];}//插入操作的实现bool insert(int& num,Heap& temp){++num;heap[num]=temp;siftUp(num);return true;}//删除操作bool removeMin(int& num,Heap& temp){if(0==num)return false;//将根的信息通过参数返回temp=heap[1];heap[1]=heap[num]; //填补树根--num;siftDown(1,num); //将根结点下滑到尾部return true;}/*******************************图****************************/const int MaxSize=10;int arr[MaxSize][MaxSize]; //存放邻接矩阵的数组int dist[MaxSize]; //到起始点长度的数组int numNode=0; //记录图中的结点个数//创建邻接矩阵void createArr(){//当边的长度为无穷大时输入一个自认为较大的数cin>>numNode;for(int i=0;i<numNode;++i)for(int j=0;j<numNode;++j)cin>>arr[i][j];}//非负权值的最短路径void Dijkstra(int v0){memset(dist,0,sizeof(dist));//初始化v0到各结点的路径值for(int i=0;i<numNode;++i)dist[i]=arr[v0][i];arr[v0][v0]=1; //将v0的访问标记置为1int num=0; //堆的大小的初始化Heap temp;//做numNode-1次求v0到各结点的操作for(int i=0;i<numNode-1;++i){//将没访问过的结点和权值压入堆中for(int k=0;k<numNode;++k){if(arr[k][k]!=1){temp.link=k;temp.dist=dist[k];insert(num,temp);}}//通过堆得到单边的情况下离v0最近的结点if(!removeMin(num,temp)) return;arr[temp.link][temp.link]=1; //将该结点访问标记置为1//以pos结点为中转，依条件改写其他结点到v0的距离for(int j=0;j<numNode;++j){if((arr[j][j]!=1)&&(arr[temp.link][j]+temp.dist<dist[j])){dist[j]=arr[temp.link][j]+temp.dist;//将修改后的关系压入堆中temp.link=j;temp.dist=dist[j];insert(num,temp);}}}//输出起始点v0与各个顶点之间的最短路径for(int i=0;i<numNode;++i)cout<<dist[i]<<" ";cout<<endl;}int main(){createArr();Dijkstra(0);}