Нужно реализовать простую программу с использованием функции алгоритма Дейкстры, как это можно сделать? void Dijkstra(int n, int **Graph, int Node){ bool *S = new bool[n]; int *D = new int[n]; int *P = new int[n]; int i, j; int Max_Sum = 0; for (i = 0; i < n; i++) for (j = 0; j < n; j++) Max_Sum += Graph[i][j]; for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (Graph[i][j] == 0) Graph[i][j] = Max_Sum; for (i = 0; i < n; i++){ S[i] = false; P[i] = Node; D[i] = Graph[Node][i]; } S[Node] = true; P[Node] = -1; for ( i = 0; i < n — 1; i++ ){ int w = 0; for ( j = 1; j < n; j++ ){ if (!S[w]){ if (!S[j] && D[j]<= D[w]) w = j; } else w++; } S[w] = true; for ( j = 1; j < n; j++ ) if (!S[j]) if (D[w] + Graph[w][j] < D[j]){ D[j] = D[w] + Graph[w][j]; P[j] = w; } } for ( i = 0; i < n; i++ ) printf("%5d",D[i]); cout << endl; for ( i = 0; i < n; i++ ) printf("%5d",P[i]+1); cout << endl; delete [] P; delete [] D; delete [] S; }
Чтобы реализовать простую программу с использованием функции алгоритма Дейкстры, вам необходимо сначала определить граф, на котором будет выполняться алгоритм. Например, можно использовать двумерный массив, где элемент [i][j] представляет вес ребра между вершинами i и j. Если между вершинами нет ребра, вес можно задать как бесконечность.
Затем вам нужно вызвать функцию Dijkstra, передав ей количество вершин в графе, сам граф в виде двумерного массива и вершину, от которой нужно найти кратчайшие пути до остальных вершин. В результате работы функции вы получите два массива: D[i] будет содержать кратчайшее расстояние от исходной вершины до вершины i, а P[i] — вершину, предшествующую вершине i на кратчайшем пути.
Вот пример простой программы на языке C++, реализующей алгоритм Дейкстры:
#include <iostream>
#include <limits.h>
using namespace std;
void dijkstra(int** graph, int src, int n)
{
bool* visited = new bool[n];
int* dist = new int[n];
int* prev = new int[n];
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = false;
prev[i] = -1;
}
dist[src] = 0;
for (int count = 0; count < n — 1; count++) {
int u = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && (u == -1 || dist[i] < dist[u]))
u = i;
}
visited[u] = true;
for (int v = 0; v < n; v++) {
int weight = graph[u][v];
if (weight != 0 && !visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
prev[v] = u;
}
}
}
for (int i = 0; i < n; i++) {
cout << «Distance from node » << src << " to node " << i << " is " << dist[i] << endl;
}
delete[] visited;
delete[] dist;
delete[] prev;
}
int main()
{
int n = 4;
int** graph = new int*[n];
for (int i = 0; i < n; i++) {
graph[i] = new int[n];
for (int j = 0; j < n; j++) {
graph[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
Этот код выводит матрицу расстояний между вершинами графа после работы алгоритма Дейкстры.
Добрый день. Меня заинтересовал ваш ответ "Чтобы реализовать простую программу с использованием функции алгоритма Дейкстры, вам необходимо снач..." на вопрос http://www.liveexpert.org/topic/view/5007957-algoritm-dejkstri. Можно с вами обсудить этот ответ?