fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <stdio.h>
  4. using namespace std;
  5. const int MaxSize = 100;
  6. const int infinity = 1000;
  7. int weigth[MaxSize][MaxSize];
  8. bool T[MaxSize]={false};
  9. int Path[MaxSize];
  10. int Vertex[MaxSize];
  11. int n;
  12. int start,finish;
  13. FILE*f;
  14.  
  15. //формирование матриц смежности
  16. void ReadData()
  17. {
  18. 	f=fopen("C:\\Users\\Mizimod\\Desktop\\matrix.txt","rt");
  19. 	fscanf(f,"%d",&n);
  20. 		for(int i=0;i<n;i++)
  21. 	       for(int j=0;j<n;j++)
  22. 	         fscanf(f,"%d",&weigth[i][j]);
  23. 	    fclose(f);     
  24. }
  25.  
  26. // вывод матриц смежности
  27. void OutPutData()
  28. {
  29. 	int i,j;
  30. 	cout<<"Матрица смежности:"<<endl;
  31. 	for(i=0;i<n;i++)
  32. 	{
  33. 	   for(j=0;j<n;j++)
  34. 		 if(weigth[i][j]==infinity)
  35. 		   cout<<setw(5)<<"-";
  36. 		 else cout<<setw(5)<<weigth[i][j];
  37. 	   cout<<endl;
  38. 	}
  39. }
  40.  
  41. //алгоритм Дейкстры
  42. void FindMinPath()
  43. {
  44. 	int i,j,Min;
  45.  
  46. 	for(i=0;i<n;i++)
  47. 	  Path[i]=infinity;
  48. 	j=start;
  49. 	T[j]=true;
  50. 	Path[j]=0;
  51.  
  52. 	while(T[finish]==false)
  53. 	{
  54. 		for(i=0;i<n;i++)
  55. 		{
  56. 			if((T[i]==false) && (Path[i]>(Path[j]+weigth[j][i])))
  57. 		{
  58. 	           Path[i]=Path[j]+weigth[j][i];
  59. 	           Vertex[i]=j;
  60. 		}	
  61. 	}
  62.  
  63. Min=infinity;
  64. j=0;
  65. for(i=0;i<n;i++)
  66.    if(!T[i] && (Min>Path[i]))
  67.    {
  68.    	Min=Path[i];
  69.    	j=i;
  70.    }
  71.  
  72. if(Min>=infinity)
  73. {
  74. 	cout<<"Нет пути от вершины"<<start<<"к веришине"<<finish<<endl;
  75. 	exit(1);
  76. }
  77. else T[j]=true;
  78. }
  79. }
  80.  
  81. //кратчайший путь
  82. void WriteMinPath()
  83. {
  84. 	cout<<"Путь:"<<endl;
  85. 	int i=finish;
  86. 	while(i!=start)
  87. 	{
  88. 		cout<<i<<"<-";
  89. 		i=Vertex[i];
  90. 	}
  91. 	cout<<start<<endl;
  92.     cout<<"Длина="<<Path[finish]<<endl; 
  93. }
  94.  
  95. int main() 
  96. {
  97. cout<<"Алгоритм Дейкстры"<<endl;
  98. ReadData();
  99. OutPutData();
  100. do
  101. {
  102. 	cout<<"Ввести номер начально вершины:";
  103. 	cin>>start;
  104. }
  105. while(start>=n);
  106. do
  107. {
  108. 	cout<<"Ввести номер конечной вершины:";
  109.     cin>>finish;
  110. }
  111. while(finish>=n);
  112. FindMinPath();
  113. WriteMinPath();
  114. }
Runtime error #stdin #stdout 0s 3512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Алгоритм Дейкстры
https://ideone.com/2clByw
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!