dijkstra.cpp

求数组最长递增子序列算法。输入一个数组

#include <iostream.h>
#define n 6
#define maxint 10000
void main()
{	int i = 0,j = 0;
	int s[n],dist[n],prev[n],c[n][n];
	int v;

	
	cout<<"Select the sourse node:";
	cin>>v;
	
	for(i = 0;i < n;i++)
		for(j = 0;j < n;j++)
		{    
			if(i == j)
				c[i][j] = 0;
			else
			    c[i][j] = maxint;
		}
	
		c[1][2] = 10; c[1][4] = 30; c[1][5] = 100;
		c[2][3] = 50; c[3][5] = 10; c[4][3] = 20;
		c[4][5] = 60;

	for(i = 0;i < n;i++)
	{
		s[i] = 0;
		dist[i] = c[v][i];
	    if(dist[i] == maxint)
			prev[i] = 0;
		else prev[i] = v;
	}

	dist[v] = 0;s[v] = 1;

	for(i = 1;i<n-1;i++)
	{
		int temp = maxint;
		int u = v; 
		for(j = 1;j<n;j++)
			if((s[j] == 0) && (dist[j] < temp))
			{
				u = j;
				temp = dist[j];
			}
		cout<<u<<endl;
		s[u] = 1;
		for(j = 1;j < n;j++)
			if((s[j] == 0) && (c[u][j] < maxint))
			{
				int newdist = dist[u] + c[u][j];
				if(newdist < dist[j])
				{
					dist[j] = newdist;
					prev[j] =u;
				}
			}
			
	}

	for(i=1;i<n;i++)
	{
		cout<<dist[i]<<" ";
	}
	cout<<endl;
}