Combinaison d'optimisation-problème typique-problème de chemin le plus court

Problème typique et méthode d'exécution

Problème routier le plus court

Lorsque $ e_ {ij} = (v_i, v_j) \ in E $ a un poids de $ a_ {ij} $ de chaque côté du graphe $ G = (V, E) $, le point de départ $ v_s \ in V $ jusqu'au point final $ Trouvez celui avec la plus petite somme de poids sur le chemin de v_t \ dans V $.

Méthode d'exécution

usage


Signature: nx.dijkstra_path(G, source, target, weight='weight')
Docstring:
Returns the shortest path from source to target in a weighted graph G.

python


#Données CSV
import pandas as pd, networkx as nx
from ortoolpy import graph_from_table
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
print(nx.dijkstra_path(g, 5, 2))

résultat


[5, 4, 0, 2]

python


# pandas.DataFrame
from ortoolpy.optimization import DijkstraPath
DijkstraPath('data/edge0.csv', 5, 2)
node1 node2 capacity weight
9 4 5 2 1
3 0 4 2 2
1 0 2 2 4

python


#Données aléatoires
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.26, 1)
print(nx.dijkstra_path(g, 0, 2))

résultat


[0, 1, 6, 3, 5, 2]

dij.png

Les données

Recommended Posts

Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Optimisation de combinaison - problème typique d'allocation généralisé
Problème d'optimisation de combinaison-problème typique d'emballage de bac
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Optimisation combinée - problème typique d'enchères combinées
Optimisation de la combinaison - problème typique - problème de débit maximal
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème de correspondance typique de problème-poids par optimisation de combinaison
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de la combinaison - problème typique - problème de coupe maximale
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Problème d'optimisation de la combinaison - coupe minimale
Combinaison de problèmes typiques d'optimisation et comment le faire