Реализации алгоритмов/Алгоритм Дейкстры

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах для нахождения кратчайшего расстояния от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

C++

Предполагается:

• visited - массив посещенных вершин( индекс равен номеру вершины);
• w - матрицы путей(хранит вес ребер), где несуществующие ребра имеют бесконечный вес;
• D - массив минимальных путей;
• INT_MAX - Максимальный размер типа int, принимаемый за бесконечность;
• st - номер источника

//Алгоритм Дейкстры
void Dijkstra(int n, int st)
{
    vector<vector<int >> w;
    w.resize(n);
    for (int i=0;i<n;i++)
        w[i].resize(n);

    bool visited[n];
    int D[n];
    for(int i=0;i<n;i++)
    {
        D[i]=w[st][i];
        visited[i]=false;
    }
    D[st]=0;
    int index=0,u=0;
    for (int i=0;i<n;i++)
    {
        int min=INT_MAX;
        for (int j=0;j<n;j++)
        {
            if (!visited[j] && D[j]<min)
            {
                min=D[j]; 
                index=j;
            }
        }
        u=index;
        visited[u]=true;
        for(int j=0;j<n;j++)
        {
            if (!visited[j] && w[u][j]!=INT_MAX && D[u]!=INT_MAX && (D[u]+w[u][j]<D[j]))
            {
                D[j]=D[u]+w[u][j];
            }
        }
    }
    cout<<"Стоимость пути из начальной вершины до остальных(Алгоритм Дейкстры):\t\n";
    for (int i=0; i<n; i++)
    {
        if (D[i]!=INT_MAX)
            cout<<st<<" -> "<<i<<" = "<<D[i]<<endl;
        else 
            cout<<st<<" -> "<<i<<" = "<<"маршрут недоступен"<<endl;
    }
}

Python 3

Предполагается:

• N — количество вершин;
• S — номер стартовой вершины (отсчитывая от нуля);
• matrix — матрица смежности исходного графа, где несуществующие рёбра имеют бесконечный вес;
• В данном случае бесконечность равна 1000000;

def Dijkstra(N, S, matrix):
	valid = [True]*N        
	weight = [1000000]*N
	weight[S] = 0
	for i in range(N):
		min_weight = 1000001
		ID_min_weight = -1
		for j in range(N):
			if valid[j] and weight[j] < min_weight:
				min_weight = weight[j]
				ID_min_weight = j
		for z in range(N):
			if weight[ID_min_weight] + matrix[ID_min_weight][z] < weight[z]:
				weight[z] = weight[ID_min_weight] + matrix[ID_min_weight][z]
		valid[ID_min_weight] = False
	return weight