Wikiszótár

súlyozott gráf

Magyar

Kiejtés

  • IPA: [ ˈʃuːjozodɡraːf]

Főnév

súlyozott gráf

  1. (matematika, gráfelmélet)

Súlyozott gráf fogalma

Egy súlyozott gráf egy olyan gráf, amelyben minden élhez egy súly (érték) van rendelve. Ez a súly általában valamilyen költséget, távolságot, időt vagy kapacitást reprezentál, és alapvetően meghatározza az algoritmusok működését, például a legrövidebb út vagy a minimális feszítőfa keresésében.


Súlyozott gráf reprezentációi Pythonban

1. Szomszédsági lista súlyokkal

weighted_graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8},
    'D': {'B': 5, 'C': 8}
}

2. Szomszédsági mátrix

import numpy as np

weighted_matrix = np.array([
    [0, 4, 2, 0],  # A
    [4, 0, 1, 5],  # B
    [2, 1, 0, 8],  # C
    [0, 5, 8, 0]   # D
])

Súlyozott gráf algoritmusok

1. Legrövidebb út keresése (Dijkstra algoritmus)

Leírás:

A Dijkstra algoritmus megtalálja a legrövidebb utat egy forráscsúcsból az összes többi csúcsba egy nem negatív súlyú gráfban.

Implementáció Pythonban:
import heapq

def dijkstra(graph, start):
    # Távolságok inicializálása
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    # Prioritási sor a csúcsokhoz
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # Ha a jelenlegi távolság nem a legrövidebb, kihagyjuk
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # Ha jobb távolságot találunk, frissítjük
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Súlyozott gráf
weighted_graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8},
    'D': {'B': 5, 'C': 8}
}

# Dijkstra futtatása
shortest_paths = dijkstra(weighted_graph, 'A')
print("Legrövidebb utak:", shortest_paths)

Kimenet:
Legrövidebb utak: {'A': 0, 'B': 3, 'C': 2, 'D': 8}

2. Minimális feszítőfa (Kruskal algoritmus)

Leírás:

A Kruskal algoritmus egy minimális feszítőfát (MST) épít súlyozott gráfokhoz. Az algoritmus éleket rendez súly szerint, és csak azokat az éleket adja hozzá, amelyek nem okoznak kört.

Implementáció Pythonban:
def kruskal(edges, num_nodes):
    # Összefoglaljuk az összefüggés vizsgálatát
    parent = {i: i for i in range(num_nodes)}

    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]

    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1

    mst = []
    edges.sort(key=lambda x: x[2])  # Rendezés súly szerint

    for u, v, weight in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, weight))

    return mst

# Súlyozott élek
edges = [
    (0, 1, 4), (0, 2, 2), (1, 2, 1),
    (1, 3, 5), (2, 3, 8)
]

# Kruskal futtatása
mst = kruskal(edges, 4)
print("Minimális feszítőfa:", mst)

Kimenet:
Minimális feszítőfa: [(1, 2, 1), (0, 2, 2), (0, 1, 4)]

3. Bellman-Ford algoritmus

Leírás:

A Bellman-Ford algoritmus akkor is működik, ha a gráfban negatív súlyú élek vannak. A Dijkstra algoritmussal ellentétben a Bellman-Ford a szélek számától függően (O(V E)) időben fut.

Implementáció Pythonban:
def bellman_ford(graph, start, num_nodes):
    distances = {node: float('infinity') for node in range(num_nodes)}
    distances[start] = 0

    for _ in range(num_nodes - 1):
        for u, v, weight in graph:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # Negatív ciklus ellenőrzése
    for u, v, weight in graph:
        if distances[u] + weight < distances[v]:
            raise ValueError("Negatív súlyú kör található a gráfban!")

    return distances

# Súlyozott élek
edges = [
    (0, 1, 4), (0, 2, 2), (1, 2, 1),
    (1, 3, 5), (2, 3, -8)  # Negatív súlyú él
]

# Bellman-Ford futtatása
try:
    shortest_paths = bellman_ford(edges, 0, 4)
    print("Legrövidebb utak:", shortest_paths)
except ValueError as e:
    print(e)

Kimenet (ha nincs negatív kör):
Legrövidebb utak: {0: 0, 1: 4, 2: 2, 3: -6}

Súlyozott gráf implementáció C++-ban

Dijkstra algoritmus C++-ban

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>

using namespace std;

vector<int> dijkstra(int n, vector<vector<pair<int, int>>> &graph, int start) {
    vector<int> distances(n, INT_MAX);
    distances[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        pq.pop();

        if (dist > distances[node]) continue;

        for (auto [neighbor, weight] : graph[node]) {
            int newDist = dist + weight;
            if (newDist < distances[neighbor]) {
                distances[neighbor] = newDist;
                pq.push({newDist, neighbor});
            }
        }
    }

    return distances;
}

int main() {
    int n = 4;
    vector<vector<pair<int, int>>> graph(n);

    // Élek hozzáadása (u, v, súly)
    graph[0].push_back({1, 4});
    graph[0].push_back({2, 2});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 5});
    graph[2].push_back({3, 8});

    vector<int> result = dijkstra(n, graph, 0);

    cout << "Legrövidebb utak:" << endl;
    for (int i = 0; i < result.size(); i++) {
        cout << "0 -> " << i << " : " << result[i] << endl;
    }

    return 0;
}

Kimenet:
Legrövidebb utak:
0 -> 0 : 0
0 -> 1 : 4
0 -> 2 : 2
0 -> 3 : 10

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=súlyozott_gráf&oldid=3480315”