dijkstra.cpp

Dijkstra算法的实现

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

#include "stdafx.h"
#include "Dijkstra.h"
#include "NodeArray.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// The one and only application object

CWinApp theApp;
const int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值

using namespace std;

void Dijkstra(int n,int v,int dist[],int prev[],int **cost);

//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{	
	int j = 0;
	int w = u;
	int count = 0;
	int *way ;
// 	way=(int *)malloc(sizeof(int)*(n+1));
	way = new int[sizeof(int)*(n+1)];
	//回溯路径
	while (w != v)
	{
		count++;
		way[count] = prev[w];
		w = prev[w];
	}
	//输出路径
	printf("the best path is:\n");
	for (j = count; j >= 1; j--)
	{
		printf("%d -> ",way[j]);
	}
	printf("%d\n",u);
	
	delete[] way;
}

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
	int nRetCode = 0;

	// initialize MFC and print and error on failure
	if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
	{
		// TODO: change error code to suit your needs
		cerr << _T("Fatal Error: MFC initialization failed") << endl;
		nRetCode = 1;
	}
	else
	{
		// TODO: code your application's behavior here.
// 		CNodeArray myNodeArray;
// 		myNodeArray.AddNode("192.168.0.221");
// 		myNodeArray.AddNode("192.168.0.206");
// 		myNodeArray.DelNode(221);
		int i,j,t;
		int n,v;
		
		int **cost;//代价矩阵
		int *dist;//最短路径代价
		int *prev;//前一跳节点空间
		
		
		printf("please input the node number: ");
		scanf("%d",&n);
		printf("please input the cost status:\n");
		
// 		cost=(int **)malloc(sizeof(int)*(n+1));
// 		
// 		for (i = 1; i <= n; i++)
// 		{
// 			cost[i]=(int *)malloc(sizeof(int)*(n+1));
// 		}
		cost = new int*[sizeof(int)*(n+1)];
		for(i=1;i<=n;i++)
		{
			cost[i] = new int[sizeof(int)*(n+1)];
		}

		//输入代价矩阵
		for (j = 1; j <= n; j++)
		{
			for (t = 1; t <= n; t++)
			{
				scanf("%d",&cost[j][t]);
			}
		}
		
// 		dist = (int *)malloc(sizeof(int)*n);
// 		prev = (int *)malloc(sizeof(int)*n);
		dist = new int[sizeof(int)*n];
		prev = new int[sizeof(int)*n];
		
		
		printf("please input the source node: ");
		scanf("%d",&v);
		//调用dijkstra算法  
		Dijkstra(n, v, dist, prev, cost);
		printf("*****************************\n");
		printf("have confirm the best path\n");
		printf("*****************************\n");
		for(i = 1; i <= n ; i++)
		{
			if(i!=v)
			{
				printf("the distance cost  from node %d to node %d is %d\n",v,i,dist[i]);
				printf("the pre-node of node %d is node %d \n",i,prev[i]);
				ShowPath(n,v,i, dist, prev);
			}
		}

		delete []dist;
		delete []prev;
		for(i=1;i<=n;i++)
			delete[] cost[i];
		delete[] cost;
	}

	return nRetCode;
}

void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
	int i;
	int j;

    int *s ;//定义具有最短路径的节点子集s
	s = new int[sizeof(int)*n];
// 	s = (int *)malloc(sizeof(int) * n);
    //初始化最小路径代价和前一跳节点值
    for (i = 1; i <= n; i++)
    {
        dist[i] = cost[v][i];
        s[i] = 0;
        if (dist[i] == maxint)
        {
            prev[i] = 0;
        }
        else
        {
            prev[i] = v;
        }
    }
    dist[v] = 0;
    s[v] = 1;//源节点作为最初的s子集
	
	
    for (i = 1; i < n; i++)
    {
        int temp = maxint;
        int u = v;
        //加入具有最小代价的邻居节点到s子集
        for (j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = 1;
        //计算加入新的节点后，更新路径使得其产生代价最短
        for (j = 1; j <= n; j++)
        {
            if ((!s[j]) && (cost[u][j] < maxint))
            {
                int newdist = dist[u] + cost[u][j];
                if (newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
        }
    }

	delete []s;
}