алгоритм dijkstra с использованием матрицы смежности

Question

В настоящее время я пытаюсь создать программу для алгоритма Дейкстры. У меня возникли проблемы с пониманием того, как создать график для алгоритма.

У меня возникли проблемы с реализацией этого графика.

Я хочу создать функцию, называемую

add_edge(G, Source, destination, weight); 

Я хочу использовать эту функцию, чтобы создать свой график таким образом, я могу позже создать случайный граф. Например, я хотел бы сделать это:

add_edge(G,1,2,3); 
add_edge(G,1,6,5); 
add_edge(G,2,3,7); 
etc. 

Первое, что я думаю сделать, это создать G, но я не уверен в том, как это сделать. Я имею в виду, чтобы сделать еще одну функцию, называемую конструкцию, которая была бы равна G, такие как:

G = construct(Vertices); 

Я просто уверен в том, как построить это.

Если кто-то может помочь мне понять эти две функции, это будет большой помощью!

Answer 1

Это один из способов сделать пй х пу массив целых чисел:

int **construct(int nx, int ny) { 
    int **a = malloc(nx * sizeof(*a)); 
    for(int i = 0; i != ny; i++) { 
     a[i] = calloc(ny, sizeof(int)); 
    } 
    return a; 
} 

Answer 2

Что G ...? Есть G Ваш ? Или Gmatrix, который вы используете для представления своего графика? Было бы больше смысла, чтобы иметь что-то вроде следующего (псевдо):

// This is your graph, represented by a 2-d array. 
// i would be your source (vertex) 
// j would be your destination (vertex) 
// graph[i][j] would be the weight of the edge between those two points 

int graph[][]; 

// Then you could add an edge to your graph with the following: 

add_edge(graph, source, destination, weight) { 
    graph[source][destination] = weight; 
} 

// A specific example would be: 

add_edge(graph, 10, 11, 5) 

Хотя вы должны знать: 2-мерные массивы в C фактически массив указателей типа p.

так ответ int **graph;

знакомства Чарли о том, как (в частности) создать matrix of ints.

Answer 3

Если вы собираетесь сделать график с использованием матрицы, перейдите к вышеупомянутым ответам. В противном случае, если вы собираетесь построить его с помощью структур, возможно, что-то подобное может вы начали

typedef struct VertexT *VertexP; 
struct VertexT 
{ 
    /*the value of the current Vertex*/ 
    int vertex; 

    /*pointer to a list of edges, each value being an end point since this 
    is a directed graph*/ 
    EdgeP edges; 

    /*pointer to a list of weights, each weight corresponding to each edge 
    thus there should be an equal number of items in both lists or there 
    is an error condition*/ 
    WeightP weights; 
} 

typedef struct GraphT *GraphP; 
struct GraphT 
{ 
    /*pointer to a list of vertices in the graph, should contain exactly 
    n vertices, where n is the number of nodes in the graph*/ 
    VertexP vertices; 
} 

Это отнюдь не единственный способ сделать это, но я хотел, чтобы обеспечить способ STRUCT в качестве альтернативы используя строго матрицы. Если это разреженный граф, использование списков может оптимизировать сложность пространства по сравнению с матрицей. Надеюсь, это поможет вам начать.

Примечание: Я использовал typedefs, потому что обнаружил, что использование VertexP или GraphP легче читать и понимать, чем struct * VertexT и struct * GraphT, это больше похоже на стилистику.

Только что просмотрел ваши изменения относительно функции addEdge(). Если бы вы собирались с моим представлением, вы можете посмотреть на псевдокоде как что-то вроде этого:

addEdge(GraphP g, int source, int dest, int weight) 
    test for g being null: 
      if true, create a graph or throw exception 
      if false, continue 
    search for source in VertexP list: 
      if true, 
       search for dest in edges 
        if true report error 
        if false add new edge and weight to list on the source VertexP 
      if false, create new VertexP with source, dest, weight and add to list