dijkstra.cpp

最短路径算法

#ifndef DIJKSTRA
#define DIJKSTRA
#include "afx.h"
#include "dijkstra.h"
int* dijkstra(int ** dig,int n)
{
    int *p=new int(n);
	for(int i=0;i<n;i++)p[i]=MAX;
	p[0]=0;

	while(1)
	{
	    //判断是否已经完成查找
		int end=0;
		for(i=0;i<n;i++)
		{
		   if(p[i]==MAX)end=1;
		}
		if(end==0)return p;

		//在已经标记的顶点中找相应的边
		for(i=0;i<n;i++)
		{
		   
			if(p[i]!=MAX)//是否标记
			{
				//查找最小边
				for(int j=0;j<n;j++)
				{
				     
					if(i==j)continue; 
					int s=p[j];
					if(dig[i][j]!=MAX)
					 {
					     if(s>p[i]+dig[i][j])
						 {
						    s=p[i]+dig[i][j];
                            p[j]=s;//标记边
						 }
					     
					 }

				}
			}

		}
	}
};
#endif