Практическая часть
#include <iostream>
#include <vector>
#include <algorithm>
#include<list>
#include<set>
#include<string>
#include<locale>
#define N 1
#define INF 10000
using namespace std;
void printGraph(int graph[N][N]) {
for (int i = 0; i < N; i++)
{
if (i < 10) {
printf("%d вершина ", i);
}
else {
printf("%d вершина ", i);
};
for (size_t j = 0; j < N; j++)
{
printf("%6d", graph[i][j]);
}
printf("\n");
}
}
void setGraph(int graph[N][N], int value) {
for (size_t i = 0; i < N; i++)
{
for (size_t j = 0; j < N; j++)
{
graph[i][j] = value;
}
}
}
class Edge {
public:
Edge() {};
Edge(int s, int f, int w) : startPoint(s), fPoint(f), weight(w) {};
int startPoint, fPoint;
int weight;
~Edge() {};
};
void printEdges(vector<Edge>& e) {
for (int i = 0; i < e.size(); i++) {
cout << e[i].weight << " ";
}
cout << endl;
}
void fillRow(int roots[N][N], int row, int col, int value) {
for (int i = col; i < N; i++) {
roots[row][i] = value;
}
}
int main()
{
setlocale(LC_ALL,”Russian”);
srand(time(0));
int graph[N][N];
setGraph(graph, 0);
vector<Edge> edges;
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
if (i != j && rand() % 3 == 1 && graph[i][j] == 0) {
graph[i][j] = rand() % 30 + 1;
edges.push_back({ i,j,graph[i][j] });
edges.push_back({ j,i,graph[i][j] });
graph[j][i] = graph[i][j];
}
}
}
for (int i = 0; i < N - 1; i++)
{
if (graph[i][i + 1] == 0) {
graph[i][i + 1] = 200;
edges.push_back({ i,i + 1,graph[i][i + 1] });
edges.push_back({ i + 1,i,graph[i][i + 1] });
graph[i + 1][i] = 200;
}
}
printGraph(graph);
cout << "Всего в графе " << edges.size() / 2 << " ребер ";
sort(edges.begin(), edges.end(), [](Edge a, Edge b) {return a.weight < b.weight ? 1 : 0; });
printEdges(edges);
int roots[N][N];
int startPoint;
int finishPoint;
cout << "Введите стартовую вершину: ";
cin >> startPoint;
cout << "Введите конечную вершину: ";
cin >> finishPoint;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
roots[i][j] = INF;
}
}
for (int i = 0; i < N; i++) {
roots[startPoint][i] = 0;
}
string msg[N];
msg[startPoint] = to_string(startPoint);
for (int step = 0; step < N - 1; step++) {
for (int i = 0; i < N; i++) {
for (auto e : edges) {
if (roots[e.startPoint][step] + e.weight < roots[e.fPoint][step + 1]) {
roots[e.fPoint][step + 1] = roots[e.startPoint][step] + e.weight;
msg[e.fPoint] = msg[e.startPoint] + "(" + to_string(e.weight) + ")" + to_string(e.fPoint);
fillRow(roots, e.fPoint, step + 1, roots[e.startPoint][step] + e.weight);
cout << "Меняем путь до вершины " << e.fPoint << " через вершину " << e.startPoint << " со стоимостью ребра " << e.weight << endl;
}
}
}
cout << "################ Итерация окончена #############" << endl;
}
printGraph(roots);
cout << "От вершины " << startPoint << " до вершины " << finishPoint << " минимальный путь стоимостью " << roots[finishPoint][N-1] << endl;
for (int i = 0; i < N; i++) {
cout << "Путь до вершины " << i << " " << msg[i] << endl;
}
}