最短パスアルゴリズムであるDijsktra(ディジェストラ)アルゴリズム.C++実装.

13個の点があり、各点から各点までの距離は以下の表の通りである.
(0,0)(1,2)(2,∞)(3,∞)(4,8)(5,∞)(6,∞)(7,∞)(8,∞)(9,4)(10,∞)(11,∞)(12,8)
(0,2)(1,0)(2,3)(3,∞)(4,∞)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,1)(11,∞)(12,∞)
(0,∞)(1,3)(2,0)(3,1)(4,∞)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,∞)(11,∞)(12,∞)
(0,∞)(1,∞)(2,1)(3,0)(4,5)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,2)(11,2)(12,∞)
(0,8)(1,∞)(2,∞)(3,5)(4,0)(5,9)(6,∞)(7,∞)(8,∞)(9,∞)(10,∞)(11,3)(12,3)
(0,∞)(1,∞)(2,∞)(3,∞)(4,9)(5,0)(6,8)(7,∞)(8,∞)(9,∞)(10,∞)(11,∞)(12,6)
(0,∞)(1,∞)(2,∞)(3,∞)(4,∞)(5,8)(6,0)(7,10)(8,1)(9,∞)(10,∞)(11,∞)(12,5)
(0,∞)(1,∞)(2,∞)(3,∞)(4,∞)(5,∞)(6,10)(7,0)(8,∞)(9,∞)(10,∞)(11,∞)(12,∞)
(0,∞)(1,∞)(2,∞)(3,∞)(4,∞)(5,∞)(6,1)(7,∞)(8,0)(9,2)(10,∞)(11,∞)(12,∞)
(0,4)(1,∞)(2,∞)(3,∞)(4,∞)(5,∞)(6,∞)(7,∞)(8,2)(9,0)(10,5)(11,∞)(12,∞)
(0,∞)(1,1)(2,∞)(3,2)(4,∞)(5,∞)(6,∞)(7,∞)(8,∞)(9,5)(10,0)(11,1)(12,∞)
(0,∞)(1,∞)(2,∞)(3,2)(4,3)(5,∞)(6,∞)(7,∞)(8,∞)(9,∞)(10,1)(11,0)(12,∞)
(0,8)(1,∞)(2,∞)(3,∞)(4,3)(5,6)(6,5)(7,∞)(8,∞)(9,∞)(10,∞)(11,∞)(12,0)
コード:

#include<limits>
#include<queue>
using namespace std;
const int max_size = 20;
class Vertex
{
    public:
		Vertex();
		void input(int number, int distance);
		queue<int> passed_way;//                  
		int output(int n);
		
	private:
		int length[max_size];
	
};
Vertex::Vertex()
{
	for(int i=0; i<max_size; i++)
		length[i] = numeric_limits<int>::max(); //int    

}
void Vertex::input(int number, int distance)//  number   distance
{

	length[number] = distance;
}

int Vertex::output(int n)//   n  
{

	return length[n];
}

 

#include"vertex.h"
class Digraph
{
	public:
		Digraph();
     	void set_distances(int s, int distance[]);
		void get_in(Vertex v, int n);
		void initial_length();

		Vertex number[max_size];
		int adjacency[max_size][max_size];
};

const int infinity = numeric_limits<int>::max();//int    

Digraph::Digraph()
{
}


void Digraph::set_distances(int s,int distance[])//   s               ，     distance 
{
	int v,w;
	bool found[13];//          s                
	for(v=0; v<13; v++)//   found、distance
	{
		found[v] = false;
		distance[v] = adjacency[s][v];// distance      s            ，         ，     0
	}
	found[s] = true;//    s      true，              
	distance[s] = 0;//               0
	for(int i=0; i<12; i++)//   13   ，  12 ，              
	{
		int min = infinity;//   min     
		for(w=0; w<13; w++)
			if(!found[w])//   s         ，   s    
				if(distance[w] < min)//distance[w]          （    ）   ，               
				{
					v = w;//          ，           
					min = distance[w];//     
				}
		found[v] = true;//     ，   s      v    
		
		number[v].passed_way.push(v);// v  vertex   passed_way      v   

		for(w=0; w<13; w++)
			if(!found[w])//   s    s    v         
				if(min + adjacency[v][w] < distance[w])//s v     +  v  s v        w               s w   （          ）
				{
					if(adjacency[v][w] != infinity)//  v w  
					{
						distance[w] = min + adjacency[v][w];//  s w   
						number[w].passed_way = number[v].passed_way;// v  vertex    passed_way   w  vertex    passed_way（passed_way       ）
					}
				}
		//for        ，   for    s     v；   for    v  ，     s     
	}
}

void Digraph::get_in(Vertex x, int n)
{
	number[n] = x;
}

void Digraph::initial_length()
{
	for(int i=0; i<max_size; i++)
		for(int j=0; j<max_size; j++)
		adjacency[i][j]=number[i].output(j);

}

 

#include"digraph.h"
#include<iostream>
#include<string>
using namespace std;
int main()
{
	Vertex a,b,c,d,e,f,g,h,i,j,k,l,m;
    a.input(0,0),a.input(1,2),a.input(4,8),a.input(9,4),a.input(12,8);
	b.input(0,2),b.input(1,0),b.input(2,3),b.input(10,1);
	c.input(1,3),c.input(2,0),c.input(3,1);
	d.input(2,1),d.input(3,0),d.input(4,5),d.input(10,2),d.input(11,2);
	e.input(0,8),e.input(3,5),e.input(4,0),e.input(5,9),e.input(11,3),e.input(12,3);
	f.input(4,9),f.input(5,0),f.input(6,8),f.input(12,6);
	g.input(5,8),g.input(6,0),g.input(7,10),g.input(8,1),g.input(12,5);
	h.input(6,10),h.input(7,0);
	i.input(6,1),i.input(8,0),i.input(9,2);
	j.input(0,4),j.input(8,2),j.input(9,0),j.input(10,5);
	k.input(1,1),k.input(3,2),k.input(9,5),k.input(10,0),k.input(11,1);
	l.input(3,2),l.input(4,3),l.input(10,1),l.input(11,0);
	m.input(0,8),m.input(4,3),m.input(5,6),m.input(6,5),m.input(12,0);

    Digraph map;
	map.get_in(a,0);
	map.get_in(b,1);
	map.get_in(c,2);
	map.get_in(d,3);
	map.get_in(e,4);
	map.get_in(f,5);
	map.get_in(g,6);
	map.get_in(h,7);
	map.get_in(i,8);
	map.get_in(j,9);
    map.get_in(k,10);
	map.get_in(l,11);
	map.get_in(m,12);

	map.initial_length();

    int array[13];
	int x = 0;//    0    
    map.set_distances(x, array);
    for(int t=0; t<13; t++)
	{
		if(t != x)//   x    
		{
			cout<<"The shortest path "<<"From place "<<x<<" to "<<t<<"is："<<x<<"-";// x t      
			while( map.number[t].passed_way.front() != t )
			{
				cout<<map.number[t].passed_way.front()<<"-";
				map.number[t].passed_way.pop();
			}
			cout<<t<<endl;;
			cout<<"The total length is："<<array[t]<<endl;
			cout<<endl;
		}
	}	
	cout<<"please input the number of place you are(0, 12): "<<endl;
		int p;
		cin>>p;
		
	    while(p<0 || p>12)
		{
		    cout<<"please input the valid number(0, 12): ";
			cin>>p;
		}
	cout<<"please input the number of place you want to(0, 12): "<<endl;
	    int q;
		cin>>q;
		while(q<0 || q>12)
		{
		    cout<<"please input the valid number(0, 12): ";
			cin>>q;
		}        
		if(p != q)
		{
			int second_array[13];
			map.set_distances(p, second_array);
		    cout<<"The shortest path "<<" from "<<p<<" to "<<q<<"passed by the following places："<<p<<"-";
			map.number[q].passed_way.pop();
			while(map.number[q].passed_way.front() != q)
			{
				cout<<map.number[q].passed_way.front()<<"-";
				map.number[q].passed_way.pop();
			}
			cout<<q<<endl;;
			cout<<"The total length is："<<second_array[q]<<endl;
			cout<<endl;
			int x;
			cin>>x;
		}        
		else
		{
			cout<<"you are the place you want to !";
			int x;
			cin>>x;	
		}
		cout<<endl;	
	return 0;
}