Member Avatar for AnnA.A

Hi,
I have graph in C. I enter vertexes and edges with price.
Now I would like add path, where I visit only few of the vertexes and then I would like to print this path. I don't know how to do it, so I am asking you here....

  • 3 Contributors
  • 3 Replies
  • 102 Views
  • 6 Days Discussion Span
  • Latest Post Latest Post by Despairy

Dani AI

Generated

Given already has a shortest-path routine, the clean approach is: turn the problem into a shortest Hamiltonian-path over the subset of required vertices (all vertices minus any excluded, e.g. vertex 4). Compute pairwise shortest distances between those required nodes (store predecessor arrays for reconstruction), then run a TSP/Hamiltonian-path solver on that small complete graph. This answers ’s “what logic?” question. ’s suggestion to negate weights is unsafe (negative cycles break shortest-path routines and negation does not yield a valid longest-simple-path solution).

Steps to implement

  1. Build an array req[] of required vertex ids (exclude 4).
  2. For each pair (i,j) call the existing shortest-path routine and fill dist[i][j]; keep per-pair predecessor info to reconstruct segments. If any dist[i][j] is INF, abort — no feasible tour through that pair.
  3. Run Held–Karp (DP with bitmasks) on the k required nodes to get the minimal visiting order (exact for k up to ~20).
  4. Expand the DP order into the full vertex sequence by concatenating the stored per-pair shortest-path sequences, skipping the duplicated join vertex at each concatenation.

Compact Held–Karp (returns indices into req[])

#include <limits.h>
#include <stdlib.h>

#define INF (INT_MAX/4)

/* dist[k][k] must contain pairwise shortest distances (INF if unreachable).
   Returns an array of length *out_len==k with indices into req[] (caller frees). */
int *held_karp_path(int k, int **dist, int *out_len) {
    int full = 1 << k;
    int *dp = malloc(full * k * sizeof(int));
    int *parent = malloc(full * k * sizeof(int));
    if (!dp || !parent) return NULL;
    for (int i = 0; i < full * k; ++i) { dp[i] = INF; parent[i] = -1; }
    for (int i = 0; i < k; ++i) dp[(1<<i) * k + i] = 0;
    for (int mask = 1; mask < full; ++mask) {
        for (int u = 0; u < k; ++u) {
            if (!(mask & (1<<u))) continue;
            int idx = mask * k + u;
            int prev_mask = mask ^ (1<<u);
            if (prev_mask == 0) continue;
            for (int v = 0; v < k; ++v) {
                if (!(prev_mask & (1<<v))) continue;
                int val = dp[prev_mask * k + v];
                if (val >= INF || dist[v][u] >= INF) continue;
                int cand = val + dist[v][u];
                if (cand < dp[idx]) { dp[idx] = cand; parent[idx] = v; }
            }
        }
    }
    int best = INF, last = -1, final_mask = full - 1;
    for (int u = 0; u < k; ++u) {
        int v = dp[final_mask * k + u];
        if (v < best) { best = v; last = u; }
    }
    if (best >= INF) { free(dp); free(parent); *out_len = 0; return NULL; }
    int *order = malloc(k * sizeof(int));
    int t = k - 1, mask = final_mask;
    while (mask) {
        order[t--] = last;
        int p = parent[mask * k + last];
        mask ^= (1<<last);
        last = p;
    }
    *out_len = k;
    free(dp); free(parent);
    return order;
}

Notes and cautions

  • Complexity: O(k^2 2^k) time, O(k 2^k) memory — practical for k up to about 20.
  • For larger k use heuristics (nearest neighbor, greedy insertion, MST-based approximations).
  • If edge weights can be negative, use Bellman-Ford or Floyd–Warshall to build dist[][]. Otherwise Dijkstra per source is fine.
  • When concatenating segments, skip the first vertex of each appended segment to avoid duplicates.

Recommended Answers

All 3 Replies

Member Avatar for deceptikon

What's the logic for the path? Is it the shortest path between A and B? Longest? Ad hoc based on input?

Member Avatar for AnnA.A

What's the logic for the path? Is it the shortest path between A and B? Longest? Ad hoc based on input?

For example, we have graph:
1-2- 3
| \ | / |
4 5 6

I already have function for shortest path. Now I want to enter shortest path, which visit all vertexes except vertex 4

Member Avatar for Despairy

so you actually want the longest path?

idea - make each "price" -1 ?

Edited by Despairy because: idea
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.