dijkstra_test.cpp

自己写的Dijkstra算法

// Dijkstra_Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "iostream.h"

#include "fstream.h"
#include <iomanip.h>

#define  MAX 100000000
#define POINT_NUM 6

bool final[POINT_NUM]={false}; //final[w]位true用来表示w点已经放入以求得最短路径的集合S
int Order[POINT_NUM]={0}; //数组用来存储点放入S集合的顺序



float min;
void ShortestPath_DIJ(int v0,float G[POINT_NUM][POINT_NUM],bool p[POINT_NUM][POINT_NUM],float d[POINT_NUM]);//Dijkstra算法定义
int main(int argc, char* argv[])
{
	float G[POINT_NUM][POINT_NUM]={  //邻接矩阵
	MAX,MAX,10,MAX,30,100,
	MAX,MAX,5,MAX,MAX,MAX,
	MAX,MAX,MAX,50,MAX,MAX,
    MAX,MAX,MAX,MAX,MAX,10,
	MAX,MAX,MAX,20,MAX,60,
	MAX,MAX,MAX,MAX,MAX,MAX
	};
	bool p[POINT_NUM][POINT_NUM]={0};  //p[v][w]如果位真，代表从V0到v当前求得的最短路径上包含w点
	float d[POINT_NUM]={0}; //用来存储最短路径长度，d[w]代表从V0到w点的最短距离


    ShortestPath_DIJ(0,G,p,d);  //调用Dijkstra函数
    cout<<"V0到V5最短距离:  "<<d[5]<<endl;
	cout<<"V0到V5最短路径:  ";
	cout<<"V0";
	for(int i=1;i<POINT_NUM;i++){
		
		if(p[5][Order[i]])
		{
		  cout<<"->"<<"V"<<Order[i];
		}
	}
	cout<<endl;
	for(int j=1;j<POINT_NUM;j++)
	{
		if(d[j]==MAX)
		cout<<"V0到V"<<j<<":  没有通路！"<<endl;
		else
	    cout<<"V0到V"<<j<<":  "<<d[j]<<endl;
	}

  ////////////////////////
//	CFile *fp;
	
	//////////////////////

    return 0;
}
void ShortestPath_DIJ(int v0,float G[POINT_NUM][POINT_NUM],bool p[POINT_NUM][POINT_NUM],float d[POINT_NUM])//Dijkstra算法实现
{
  for(int v=0;v<POINT_NUM;v++)
  {
    final[v]=false;  //初始化
	d[v]=G[v0][v];
	for(int w=0;w<POINT_NUM;w++)
		p[v][w]=false;
	if(d[v]<MAX)
	{
	  p[v][v0]=true;
	  p[v][v]=true;
	}
  }
  d[v0]=0; //初始化V0到V0本身的距离位0
  final[v0]=true;//先把V0放入集合S
  Order[0]=v0;  //V0的值也先存储起来
  for(int i=1;i<POINT_NUM;i++)
  {
    min=MAX;
  	for(int w=0;w<POINT_NUM;w++)
	{
	  if(!final[w])  //如果点w在集合V-S中
	  {
	     if(d[w]<=min)  //并且当前V0点到w的距离更近
		 {
		   v=w;
		   min=d[w];
		 }
	  }
	
	}
	final[v]=true;//离V0点最近的v点放入集合S
	Order[i]=v;  //放入的该点的值（序号）也按序存储起来
	for(w=0;w<POINT_NUM;w++)  //更行当前最短路径及距离
	{
		if(!final[w]&&min+G[v][w]<d[w])
		{
		  d[w]=min+G[v][w];
		  for(int i=0;i<POINT_NUM;i++)
		  {
		       p[w][i]=p[v][i];
		  }
		  p[w][w]=true;
		}
	
	}
  }

}