pycharm不会啊
问题遇到的现象和发生背景
遇到的现象和发生背景，请写出第一个错误信息
用代码块功能插入代码，请勿粘贴截图。 不用代码块回答率下降 50%
运行结果及详细报错内容
我的解答思路和尝试过的方法，不写自己思路的，回答率下降 60%
我想要达到的结果，如果你需要快速回答，请尝试 “付费悬赏”
Python建立有向带权图：
可参考
import re
class Vertex:
# 邻接列表构图，每个node保存与本节点相连的节点
def __init__(self, key):
# 顶点的key
self.id = key
# 用于保存和哪些点相连，key为node的key，val为连接权重
self.connectedTo = {}
def addNeighbor(self, nbr, weight=0):
# 添加与某个node的连接，连接key为该节点key，值为权重
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
# 获取与本节点相连的所有节点key
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self, nbr):
return self.connectedTo[nbr]
class Graph:
def __init__(self):
# 顶点集合
self.vertList = {}
# 顶点的数量
self.numVertices = 0
def addVertex(self, key):
# 添加顶点数量
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
# 这的key就是代表这个顶点的变量
self.vertList[key] = newVertex
# 此处为什么要将这个顶点返回呢
return newVertex
def getVertex(self, n):
# 遍历图中所有的顶点
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self, n):
# 判断图中是否存在这个顶点
return n in self.vertList
def addEdge(self, f, t, cost=0):
# 给两个顶点添加边
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
# 获取所有的边
def getVertices(self):
return self.vertList.keys()
# 遍历这个图结构
def __iter__(self):
return iter(self.vertList.values())
g = Graph()
for i in range(6):
g.addVertex(i)
print(g.vertList)
g.addEdge(0, 1, 5)
g.addEdge(0, 5, 2)
g.addEdge(1, 2, 4)
g.addEdge(2, 3, 9)
g.addEdge(3, 4, 7)
g.addEdge(3, 5, 3)
g.addEdge(4, 0, 1)
g.addEdge(5, 4, 8)
g.addEdge(5, 2, 1)
for v in g:
for w in v.getConnections():
temp=w.getId()
number=g.vertList[w.getId()]
print("( %s , %s , %s )" % (v.getId(), w.getId(), v.connectedTo[number]))
这个实例主要提供方法【Python 最短路径的几种求解方式】，链接：https://www.jb51.net/article/244588.htm
已a到c为例:
from itertools import groupby
def findAllPath(graph, start, end, path=[]):
# path.append(start)
path = path + [start]
if start == end:
return path
for node in graph[start]:
if node not in path:
newpaths = findAllPath(graph, node, end, path)
for newpath in newpaths:
if newpath == end:
path.append(newpath)
paths.append(path)
return paths
def get_graph(graph_dict):
# 打散, 获取相关的两个点
t = [(kvs[0], v) for kvs in graph_dict.items() for vs in kvs[1] for v in vs]
# 反转两个点, 获取2个点的相互关系
t_re = [(t2[1], t2[0]) for t2 in t]
t.extend(t_re)
# 聚合得到每个点的下个点
t_g = groupby(sorted(t, key=lambda x: x[0]), key=lambda x: x[0])
# 每个点的所有直接连接点
t_dict = {k: [v[1] for v in list(vs)] for k, vs in t_g}
return t_dict
if __name__ == '__main__':
# 图
graph = {
'a': ['b', 'c', 'd'],
'b': ['c', 'd'],
'c': ['d', 'e'],
'd': ['e'],
'e': ['b', 'd']
}
# 权 以 a 到 c 为例, 其他点需要补充
quan = {
'a-b': 5,
'b-c': 2,
'a-c': 9
}
t_dict = get_graph(graph)
start, end = 'a', 'c'
paths = [] # 存储所有路径
findAllPath(t_dict, start, end)
paths_result=[]
for vs in paths:
len_sum = 0
for i, v in enumerate(vs):
if i < len(vs)-1:
len_sum += quan.get(f'{vs[i]}-{vs[i+1]}')
paths_result.append(["-".join(vs), len_sum])
print(f'start: {start}, end: {end}, result: {paths_result}')
输出:
start: a, end: c, result: [['a-b-c', 7], ['a-c', 9]]
pycharm求带权有向图的最短路径以及长度
如有帮助，望采纳
#include <iostream>
#include <iomanip>
using namespace std;
#include "Graph.h"
void main()
{
int i, n;
cout << "输入你所输入的有向带权图的顶点个数: ";
cin >> n;
adjmatrix g;
InitMatrix(g);
CreateMatrix(g);
cout << "你输入的有向带权图的邻接矩阵表示为: " << endl;
PrintMatrix(g, n);
int * d = new int [n];
edgenode ** path = new edgenode * [n];
cout << "请输入你要输入的源点: ";
cin >> i;
Dijkstra(g, d, path, i, n);
PrintPath(d, path, i, n);
}
//***********Graph.h**********************
#define MaxVerNum 20
#define MaxValue 10000
typedef int adjmatrix[MaxVerNum][MaxVerNum]; //邻接矩阵的类型定义
typedef struct Node
{
int adjvex;
struct Node * next;
}edgenode; //指针数组path[]基类型定义
//初始化邻接矩阵表示的有向带权图
void InitMatrix(adjmatrix G)
{
int i, j;
for(i = 0; i < MaxVerNum; i++)
for(j = 0; j < MaxVerNum; j++)
G[i][j] = MaxValue;
}
//建立邻接矩阵表示的有权带向图(即通过输入图的每条边建立图的邻接矩阵)
void CreateMatrix(adjmatrix G)
{
int i, j, x;
cout << "请输入顶点和相应的权值: " << endl;
cin >> i >> j >> x;
while(i != -1)
{
G[i][j] = x;
cin >> i >> j >> x;
}
}
//输出邻接矩阵表示的有向带权图(即输出图的每条边)
void PrintMatrix(adjmatrix G, int n)
{
int i, j;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
if(G[i][j] == MaxValue)
cout << setiosflags(ios::left) << setw(5) << "Inf";
else
cout << setiosflags(ios::left) << setw(5) << G[i][j];
}
cout << endl;
}
}
void Path(edgenode * path[], int m, int j)
{
edgenode * p, * q, *s;
p = path[j];
while(p != NULL)
{
path[j] = p->next;
delete p;
p = path[j];
}
p = path[m];
while(p != NULL)
{
q = new edgenode;
q->adjvex = p->adjvex;
if(path[j] == NULL)
path[j] = q;
else
s->next = q;
s = q;
p = p->next;
}
q = new edgenode;
q->adjvex = j;
q->next = NULL;
s->next = q;
}
//求最短路径的Dijkstral算法
void Dijkstra(adjmatrix GA, int dist[], edgenode *path[], int i, int n)
{
int j, k, w, m;
bool * s = new bool[n];
for(j = 0; j < n; j++)
{
if(j == i)
s[j] = true;
else
s[j] = false;
dist[j] = GA[i][j];
if(dist[j] < MaxValue && j != i)
{
edgenode * p1 = new edgenode;
edgenode * p2 = new edgenode;
p1->adjvex = i;
p2->adjvex = j;
p2->next = NULL;
p1->next = p2;
path[j] = p1;
}
else
path[j] = NULL;
}
for(k = 1; k <= n-2; k++)
{
w = MaxValue;
m = i;
for(j = 0; j < n; j++)
if(s[j] == false && dist[j] < w)
{
w = dist[j];
m = j;
}
if(m != i)
s[m] = true;
else
break;
for(j = 0; j < n; j++)
if(s[j] == false && dist[m] + GA[m][j] < dist[j])
{
dist[j] = dist[m]+GA[m][j];
Path(path, m, j);
}
}
delete []s;
}
//输出从源点到每个顶点的最短路径及长度的函数
void PrintPath(int dist[], edgenode * path[], int i, int n)
{
int j;
for(j = 0; j < n; j++)
{
if(i != j)
{
cout << "顶点v" << i << "到顶点v" << j << "的最短路径的长度为 "
<< dist[j] << ", 最短路径为: ";
edgenode * p = path[j];
while(p != NULL)
{
cout << setw(4) << p->adjvex;
p = p->next;
}
cout << endl;
}
}
}